3076. 填数游戏

【题目描述】

小 P 和小 Z 经常在一起切磋智商，今天他们在玩填数游戏。

现在有一张n*m的矩阵，矩阵中每个格子只能填1或-1，小 P 已经提前在矩阵中填好了k个格子，现在他问小 Z，有多少种不同的方法填剩下的格子，使得矩阵满足任意一行或一列中所有数的积都是-1？（两种方法不同当且仅当两种方法中某个格子填的数不同）。小 Z 乞求小 P 降低题目难度，于是小 P 又给出了一个条件，k严格小于n和m的最大值，且最后的答案模p就可以了。“聪明”的小 Z 还是不会做，于是他找到了你。

【输入格式】

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

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

接下来k行，每行三个整数a,b,c，代表第a行，第b列，填了数c。

最后一行包含一个整数p，代表需要将答案模p。

【输出格式】

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

【样例输入1】

2 2
1
2 2 -1
2333

【样例输出1】

1

【样例输入2】

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

【样例输出2】

195328496

【样例1说明】

2×2 的矩阵，右下角填了-1，所以只有

-1 1

1 -1

这一种填法。

【数据规模与约定】

对于 30%的数据，1 ≤ n*m ≤ 21。

对于 70%的数据，1 ≤ n,m ≤ 1000。

其中有 10%的数据，1 ≤ n,m ≤ 1000,k = 0

对于 100%的数据，1 ≤ n,m ≤ 1000000,

0 ≤ k < max (n,m),

1 ≤ a ≤ n, 1 ≤ b ≤ m, c∈ {1,-1},

2 ≤ p ≤ 10^9 + 7,

数据保证不会出现一个格子填两次。