首先如果没有限制的话，我们可以直接求出答案，假设对于n*m的矩阵，我们最上方一行和左方的一列随意确定，那么首先这写确定的状态肯定是不会不合法的，因为我们可以调整剩下的01状态来使得这一行一列的状态合法，而且剩下的01状态唯一确定，我们叫最上面的行和左面的列为标准行列，那么我们对于每一种不同的标准行列都可以有一组合法解，那么最后答案的数量就是标准行列的数量，那么标准行列一共有2^(n+m-1)种方案，那么这就是最后的答案。
那么每一个四方阵的1个数为奇数代表这个四方阵的xor和为1，那么根据xor的结合律，我们可以得到一个式子，假设a[i][j]为合法方案中[i][j]位置的数，那么a[1][1]^a[i][j]^a[1][j]^a[i][1]=0或1，当且仅当i,j都为偶数的时候等于0，那么有了这个性质我们可以根据给出的限制判断[1][j]和[i][1]位置的01选择是否相同，那么我们可以将标准行列的每一个点看成两个点，即这个位置选的是0还是1，那么根据给出的限制我们可以知道在这个点选0或1时其余某些点必须选0或1，那么这就是一个简单的2-sat模型了，我们可以连出图之后判断各个连通块中是否有不同的颜色（即题目直接对标准行列做限制），有的话即无解，那么我们可以确定出独立点的个数，即这些点的颜色确定不会对其他点造成影响。
对于左上角选1的情况我们只需要把限制中的01状态全部取xor然后再按照上述方法做一遍就可以了。
那么在实际操作的时候我们可以用并查集来维护及节点之间的信息，设father[x]为x的父亲节点，ww[x]为x与其父亲节点的关系，ww[x]为0时代表颜色相同，1时则不同，那么我们只需要维护这个就可以了。
备注：在合并a,b的时候，设fa为a的父亲应该ww[fa]=ww[a]+ww[b]+a,b节点之间的关系(为01)，结果开始的时候忘了ww[a]了，改了之后又把ww[b]删了，查了半天= =。
/**************************************************************
Problem: 2303
User: BLADEVIL
Language: C++
Result: Accepted
Time:1340 ms
Memory:71120 kb
****************************************************************/ //By BLADEVIL
#include <cstdio>
#include <cstring>
#define maxn 3000010
#define d39 1000000000
#define LL long long using namespace std; struct rec {
int x,y,z;
}ask[maxn]; int n,m,N,k,w,ans;
int flag[maxn],father[maxn],ww[maxn]; int getfather(int x) {
if (father[x]==x) return x;
int fa=father[x];
father[x]=getfather(fa);
ww[x]=(ww[x]+ww[fa])%;
return father[x];
} int pwr(int x,int k) {
int ans=;
while (k) {
if (k&) ans=(LL)ans*x%d39;
k>>=;
x=(LL)x*x%d39;
}
return ans;
} int calc() {
memset(flag,,sizeof flag);
memset(ww,,sizeof ww);
N=n+m-;
for (int i=;i<=N;i++) father[i]=i;
for (int i=;i<=k;i++) {
if (ask[i].x==) {
int cur;
if (ask[i].z) cur=; else cur=;
if (flag[ask[i].y-]) {
if (flag[ask[i].y-]!=cur) return ; else flag[ask[i].y-]=cur;
} else flag[ask[i].y-]=cur;
continue;
}
if (ask[i].y==) {
int cur;
if (ask[i].z) cur=; else cur=;
if (flag[ask[i].x+m-]) {
if (flag[ask[i].x+m-]!=cur) return ; else flag[ask[i].x+m-]=cur;
} else flag[ask[i].x+m-]=cur;
continue;
}
int a=ask[i].y-,b=ask[i].x+m-;
//printf("%d %d\n",a,b);
int fa=getfather(a),fb=getfather(b),add=;
if ((ask[i].x%==)&&(ask[i].y%==)) {
if (ask[i].z) add=; else add=;
} else {
if (ask[i].z) add=; else add=;
}
//printf("%d\n",add);
if (fa==fb) {
int cur=(ww[a]+ww[b])%;
if (cur!=add) return ;
} else father[fa]=fb; ww[fa]=(ww[b]+ww[a]+add)%;
//for (int i=1;i<=N;i++) printf("|%d %d %d %d\n",i,father[i],ww[i],flag[i]);
}
//for (int i=1;i<=N;i++) printf("|%d %d %d\n",i,father[i],ww[i]);
//for (int i=1;i<=N;i++) printf("%d ",flag[i]); printf("\n");
int cnt=;
for (int i=;i<=N;i++) if (father[i]==i) cnt++;
//printf("%d ",cnt);
for (int i=;i<=N;i++) if (flag[i]) {
if (!flag[getfather(i)]) flag[getfather(i)]=(flag[i]+ww[i])%+; else
if (flag[getfather(i)]!=(flag[i]+ww[i])%+) return ;
}
//for (int i=1;i<=N;i++) printf("%d ",flag[i]); printf("\n");
for (int i=;i<=N;i++) if ((father[i]==i)&&(flag[i])) cnt--;
//printf("%d\n",cnt);
return pwr(,cnt);
} int main() {
scanf("%d%d%d",&n,&m,&k);
for (int i=;i<=k;i++) scanf("%d%d%d",&ask[i].x,&ask[i].y,&ask[i].z);
for (int i=;i<=k;i++) if ((ask[i].x==)&&(ask[i].y==)) w=i;
//calc(); return 0;
if (w) {
if (ask[w].z)
for (int i=;i<=k;i++) ask[i].z^=;
ans=calc();
} else {
ans=calc()%d39;
for (int i=;i<=k;i++) ask[i].z^=;
(ans+=calc())%=d39;
}
printf("%d\n",ans);
return ;
}