Description：

给一个 $n\times m$ 的表格，每个位置是 $1$ 或 $-1$ ，每一行或一列的积都是 $-1$ ，其中给出了 $k$ 个格子的值，问有多少种满足条件的表格。

$1\le n,m\le 1000,1\le k<\max(n,m)$

Solution：

$k<\max(n,m)$ 这个限制有什么意义，这意味着整张表格一定有一行或一列是空的，那么我们可以先满足所有的行或列，再用最后这个满足列或行，所以答案其实就是 $2^{(n-1)\times (m-1)-k}$ ，注意有很多特判，比如某一行被摆满了或者 $n+m$ 为奇数则不合法。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,m,k,p;

#define MAXN 1010

int cntcol[MAXN],cntrow[MAXN],rescol[MAXN],resrow[MAXN];

int power[MAXN];

int main()

{

	scanf("%d%d",&n,&m);

	if((n + m) % 2 == 1)

	{

		puts("0");

		return 0;

	}

	for(int i = 1;i <= n;++i)rescol[i] = 1;

	for(int i = 1;i <= m;++i)resrow[i] = 1;

	scanf("%d",&k);

	int a,b,c;

	for(int i = 1;i <= k;++i)

	{

		scanf("%d%d%d",&a,&b,&c);

		++cntcol[a];++cntrow[b];

		rescol[a] *= c;resrow[b] *= c;

	}

	for(int i = 1;i <= n;++i)

	{

		if(cntcol[i] == m && rescol[i] == 1)

		{

			puts("0");

			return 0;

		}

	}

	for(int i = 1;i <= m;++i)

	{

		if(cntrow[i] == n && resrow[i] == 1)

		{

			puts("0");

			return 0;

		}

	}

	scanf("%d",&p);

	long long ans = 1;

	if(n < m)

	{

		swap(n,m);

		swap(cntrow,cntcol);

		swap(resrow,rescol);

	}

	power[0] = 1;

	for(int i = 1;i <= n;++i)power[i] = power[i - 1] * 2 % p;

	bool tag = false;

	for(int i = 1;i <= n;++i)

	{

		if(cntcol[i] == 0 && !tag)

		{

			tag = true;

			continue;

		}

		if(cntcol[i] == m)continue;

		ans = ans * power[m - cntcol[i] - 1] % p;

	}

	cout << ans << endl;

	return 0;

}