感觉题解区里的形式化解法不是人类能够想到的，这里给出一个比较容易理解的解题过程。

思路

没有已经染色的格子限制

思考整个问题的简化版，假设 $n=2$，且没有已经染色的限制，则答案怎么求？我们进行一个简单的分类讨论：

• 如果第一列的两个格子颜色不同：则下一列的颜色必然相同，再下一列的各自颜色必然不同，以此类推，而对于每一列，显然有 $2$ 种不同的涂色方案，则共有 $2^m$ 次方种涂色方案。
• 如果第一列的两个格子颜色相同：则下一列的颜色必然不同，再下一列的各自颜色必然相同，以此类推，而对于每一列，显然有 $2$ 种不同的涂色方案，则共有 $2^m$ 次方种涂色方案。

综上，显然是有 $2^{m+1}$ 种不同的涂色方案的。

这时，我们考虑把 $n$ 放大，看看会发生什么：

• 首先，第一列的涂色情况是没有限制的，所以方案数是 $2^n$。
• 而对于第 $i+1$ 列来说，其涂色方法是依赖于第 $i$ 列的，就像 $n=2$ 时，如果上下相邻两个格子在上一行里颜色相同，则在这一行里颜色就不同，否则就直接反过来。而这时，如果你确认了第一行的格子颜色是什么，你就可以根据这个方法把这一列里所有的格子全部确认下来。
• 于是每一列又有了 $2$ 种方案，最终用乘法原理乘起来就是 $2^{n+m-1}$ 种情况了。

正解

分析一下上述部分的关键：如果上下相邻两个格子在上一行里颜色相同，则在这一行里颜色就不同，否则相反。

观察该条性质的实质，通过手玩一下格子即可看出来，若用 $0,1$ 分别表示红色和蓝色，则上述过程完全等价于：将上一列的所有奇数行或者偶数行取反。

此时，我们便可以来理解限制对答案的影响：

• 如果某一列中有至少一个被涂色了的格子，则无论上一列是什么，想要推得这一列的情况至多只会有一种操作方式，也就是说在上一列已知的情况下，这一列最多只有一种情况。证明是容易的，随便选取一个被涂色了的点，如果该点和上一行的点颜色一样，则进行取反时就不能对该点所在的奇偶性进行取反，剩下的几种情况也是一样的。
• 如果某一列中只有一个被涂色了的格子，则其对上一行实际上没有要求，无论如何都不会产生冲突，这里的产生冲突是指导致不存在符合条件的涂色方案。
• 如果某一列中有多个被涂色的了格子，则我们随机选取两个格子：
  • 如果这两个格子所在的行奇偶性相同，则在第一列中，对应行上的格子颜色是否相同与这两个格子是一样的。
  • 如果这两个格子所在的行奇偶性不同，则在第一列中，对应行上的格子颜色是否相同是取决于这两个格子的，具体来说：
    • 如果这一列是奇数列：则在第一列中，对应行上的格子颜色是否相同与这两个格子是相反的。
    • 如果这一列是偶数列：则在第一列中，对应行上的格子颜色是否相同与这两个格子是一样的。

于是，我们能够把所谓的涂色限制，转化为在第一列中某两个格子的颜色是否一样，这个东西就很简单了，显然用一个扩展域并查集维护即可。

而对于某一列中的多个限制来说，不难发现其具有传递性，所以我们实际上不需要对任意两个限制进行转化，只需要对上下相邻的限制转化即可。

综上所述，则我们能够求得最终答案为：

• 如果条件出现了冲突，即没有满足条件的涂色方案，输出 0。
• 否则，统计第一列的连通块个数，注意要去掉那些已经确认了颜色的块数，记其为 $c_1$；记第 $2$ 到 $m$ 列中没有涂色限制的列的个数为 $c_2$。输出 $2^{c_1+c_2}$ 即可。

代码

这个铸币笔者把 merge_ 打错了，导致调了一个下午，大家都快来嘲笑他。

#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;
const ll N=1e6+10;
const ll MOD=1000000000;
ll fa[N<<1],n,m,k;
void init(){for(ll i=1;i<=(n<<1);i++) fa[i]=i;}
ll findf(ll x){return (fa[x]==x)?x:fa[x]=findf(fa[x]);}
void merge_(ll x,ll y){
	ll fx=findf(x),fy=findf(y);
	if(fy!=fx) fa[fy]=fx;
}
pair<ll,bool> lst[N];
struct node{ll x,y;bool col;}dot[N];
inline bool cmp(node x,node y){return x.x<y.x;}
ll ans=1;
bool vis[N];
ll clc[N],p1,p2;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>m>>k;
	init();
	for(ll i=1;i<=k;i++) cin>>dot[i].x>>dot[i].y>>dot[i].col;
	sort(dot+1,dot+1+k,cmp);
	for(ll i=1;i<=k;i++){
		ll L=dot[i].y;
		if(lst[L].first){
			if(lst[L].first%2==dot[i].x%2){
				if(lst[L].second==dot[i].col) merge_(lst[L].first,dot[i].x),merge_(lst[L].first+n,dot[i].x+n);
				else merge_(lst[L].first,dot[i].x+n),merge_(lst[L].first+n,dot[i].x);
			}
			else{
				if(lst[L].second==dot[i].col) merge_(lst[L].first,dot[i].x+((L+1)&1)*n),merge_(lst[L].first+n,dot[i].x+(L&1)*n);
				else merge_(lst[L].first,dot[i].x+(L&1)*n),merge_(lst[L].first+n,dot[i].x+((L+1)&1)*n);
			}
		}
		lst[L].first=dot[i].x,lst[L].second=dot[i].col;
	}
	for(ll i=1;i<=n;i++){
		ll f=findf(i),nf=findf(i+n);
		if(f==nf){cout<<"0";return 0;}
	}
	for(ll i=1;i<=k;i++){
		ll L=dot[i].y;if(L!=1) continue;
		ll f=findf(dot[i].x),nf=findf(dot[i].x+n);
		if(!vis[f]){
			vis[f]=1;vis[nf]=1;
			clc[f]=dot[i].col+1;clc[nf]=(dot[i].col^1)+1;
		}
		else if(clc[f]!=dot[i].col+1||clc[nf]!=(dot[i].col^1)+1){cout<<"0";return 0;}
	}
	ll cnt=0,ccnt=0;
	for(ll i=1;i<=n;i++){
		ll f=findf(i),nf=findf(i+n);
		if(vis[f]) continue;
		vis[f]=vis[nf]=1;
		cnt++;
	}
	for(ll i=2;i<=m;i++) if(!lst[i].first) ccnt++;
	cnt+=ccnt;
	while(cnt--) ans=(ans<<1)%MOD; 
	cout<<ans;
	return 0;
}