顺着容斥的标签摸进来的。

思考如何容斥：一开始想的是用 $2^{n\times m-k}$ 减掉不合法的情况，发现难度是 NOI/NOI+/CTSC 的。

那么先抛开容斥的问题，想怎么计算更简便，不难发现正着算还更容易。

一个显而易见的结论是：所有合法的情况第一行或第一列必须是正负交替的。

在证明前，给一个性质：如果相邻两格填了一样的电子，那这一行/列就确定了。大概就是这样：

+?????...  ->     +-+-+-...
+?????...  ->     +-+-+-...

用反证法好证。如果第一行和第一列都不是正负交替的，那么至少有连续的两个相同符号，所以就会出现这样的情况：

...++...
...--...
-+-!!...
-+-!!...
........
........

在交叉的四个感叹号的位置矛盾了，所以得证。

然后发现如果第一行是正负交替的，那第二列也一定是正负交替的，而有 $2$ 种情况：先放正和先放负。列同理。

可以根据给定的 $k$ 个点确定每一行每一列有无约束（根据这个点的 $x$ 和 $y$ 可以得出这一行（列）要先放正还是先放负）和是否矛盾，开两个 map 记录即可。

最后要注意的一个点是：在行和列的约束都不矛盾时，如果 $k=0$，那么有两种（左上角是 + 和是 -）第一行和第一列都是正负交替的情况会被算两次，答案减 $2$。如果 $k>0$，那么答案只用减 $1$（一定有 $1$ 种恰好不会取到）。

然后就做完了。

怎么没用容斥啊？标签是不是错了。

（打开题解）诶原来最后减掉的 $2$ 种叫容斥啊！

涨知识了。

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int P=1e9+7;
map <int,int> h,l;
int qpow(int x,int y){
	if(y==0) return 1;
	if(y==-1) return 0;
	int res=1;
	while(y>1){
		if(y%2==1) res=res*x%P;
		y/=2,x=x*x%P;
	}
	return x*res%P;
}
signed main(){
	char c;
	int n,m,k,x,y,flagx=0,flagy=0,ans=0,cntx=0,cnty=0;
	cin>>n>>m>>k;
	for(int i=1;i<=k;i++){
		cin>>c>>x>>y;
		bool t=x%2,o=y%2;
		if(c=='+') t=(x+1)%2,o=(y+1)%2;
		if(h[y]==0) h[y]=t+1,cnty++;
		else if(h[y]!=t+1) flagy=1;
		if(l[x]==0) l[x]=o+1,cntx++;
		else if(l[x]!=o+1) flagx=1;
	}
	if(flagx==0) ans=ans+qpow(2,n-cntx);
	if(flagy==0) ans=ans+qpow(2,m-cnty);
	if(flagx==0&&flagy==0){
		if(k==0) ans-=2;
		else ans--;
	}
	cout<<(ans+P)%P;
	return 0;
}

这是蒟蒻的第 $22$ 篇题解，感谢观看。