4025. 正负游戏

【题目描述】

给你一个$n\times m$的矩阵，矩阵中每一个格子只能填1或-1，已知矩阵中已经填好了$k$个格子，问你有多少种不同的方法填剩下的格子，使得矩阵满足任意一行或一列中所有数的积都是-1?(两种方法不同当且仅当两种方法中某个格子填的数不同)

考虑到解决问题的时间，我们设定已经填的格子数$k$严格小于$n$和$m$的最大值。

明显，方法种数可能很大，你只需要模上998244353就可以了。

【输入格式】

输入第一行包含两个整数$n$和$m$，代表矩阵的大小。

第二行包含一个整数$k$，代表已经填好的格子数。

接下来$k$行，每行三个整数$x,y,z$，代表第$x$行第$y$列填了数字$z$。

【输出格式】

输出只有一行，一个整数表示最后的答案。

【样例输入1】

2 2
1
2 2 -1

【样例输出1】

1

【杨例1解释】

$2\times 2$的矩阵，右下角填了-1，所有只有

-1 1

1 -1

这一种填法。

【样例输入1】

983 533
3
1 3 1
4 2 -1
100 100 1

【样例输出1】

194151410

【样例下载】

【数据规模与约定】

对于30%的数据，$1\leq n\times m\leq 21$。

对于70%的数据，$1\leq n,m\leq 1000$。

其中有10%的数据，$1\leq n,m\leq 1000,k=0$。

对于100%的数据，$1\leq n,m\leq 10^6，0\leq k<\max(n,m),1\leq x\leq n, 1\leq y\leq m,z\in\{1,-1\}$。

数据保证每个格子只会填一次。