1046: 吹响！悠风号

音乐原本，并非为向对手炫耀自己的实力而存在的，然而现在在这里的众多其他学校的学生及观众，尚不了解北宇治的实力。所以老师认为，今天会是让大家领略我们实力的好机会，好了，去向大家展现我们北宇治的实力吧。

——《吹响！悠风号》

给你一个 $n$ 个行，$m$ 列的棋盘，每个位置都要填上 $1$ 或者 $-1$。其中有 $k$ 个位置以及填上了数，而其它的位置则等待你来填写。并且这个棋盘满足 $k$ 严格小于 $\max(n,m)$。

一个棋盘是和谐的，当且仅当每一行每一列乘积都是 $-1$。

求和谐的棋盘种类数，答案对 $p$ 取模。

第一行一个整数 $T$ 表示数据组数。

对于每一组数据有以下输入:

第一行两个整数 $n,m$ 表示纸上是一个 $n\times m$ 的网格图。

第二行一个整数 $k$，表示已经有 $k$ 个位置填了数。

下面 $k$ 行，每行 $3$ 个正整数$x,y,c$，表示第 $x$ 行第 $y$ 列被填上了 $c$。保证没有重复位置出现。

接着一行一个整数 $p$。

对于每组数据输出一个整数，表示方案数模 $p$ 后的结果。

``` 2 2 2 1 1 1 -1 100 2 2 0 100

```

``` 1 2

```

对于 $30\%$ 的数据，保证$1\leq n\times m\leq 15$。

对于 $100\%$ 的数据，保证$1\leq n,m\leq 10^3$。

保证所有数据满足 $0\leq k\leq \max(n,m),c\in {-1,1},2\leq p\leq 10^9+7,1\leq T\leq 5$。

Oops! 本题目还没有解答！

助教老师们编题的速度，已经超过了解题的速度！

OJ翻了一新，但本解答集还大多用的是2017-2019级，甚至更早的同学们贡献的答案。

如果你已经AC了，可以的话，请您参考添加页面，与大家一起分享你的题解！