CF40E.Number Table

As it has been found out recently, all the Berland's current economical state can be described using a simple table n × m in size. n — the number of days in each Berland month, m — the number of months. Thus, a table cell corresponds to a day and a month of the Berland's year. Each cell will contain either 1, or -1, which means the state's gains in a particular month, on a particular day. 1 corresponds to profits, -1 corresponds to losses. It turned out important for successful development to analyze the data on the state of the economy of the previous year, however when the treasurers referred to the archives to retrieve the data, it turned out that the table had been substantially damaged. In some table cells the number values had faded and were impossible to be deciphered. It is known that the number of cells in which the data had been preserved is strictly less than max(n, m). However, there is additional information — the product of the numbers in each line and column equaled -1. Your task is to find out how many different tables may conform to the preserved data. As the answer to the task can be quite large, you have to find it modulo p.

最近发现，贝兰国当前的经济状况可用一个大小为 $n \times m$ 的简单表格来描述：其中 $n$ 表示贝兰国每个月的天数，$m$ 表示一年中的月份数。因此，表格中的每个单元格对应贝兰国一年中的某一天和某一月。每个单元格中包含的值为 $1$ 或 $-1$，分别表示该月该日国家的盈利或亏损：$1$ 表示盈利，$-1$ 表示亏损。
对上一年经济状况数据进行分析，对国家的顺利发展至关重要。然而，当财政官员查阅档案以获取这些数据时，却发现该表格已严重损坏：部分单元格中的数值已经褪色，无法辨认。已知数据得以保留的单元格数量严格小于 $\max(n,\,m)$。但还有额外信息：每行及每列中所有数字的乘积均等于 $-1$。
你的任务是计算有多少种不同的表格可能与所保留的数据相容。由于答案可能非常大，你只需输出其对 $p$ 取模的结果。

The first line contains integers n and m (1 ≤ n, m ≤ 1000). The second line contains the integer k (0 ≤ k < max(n, m)) — the number of cells in which the data had been preserved. The next k lines contain the data on the state of the table in the preserved cells. Each line is of the form "a b c", where a (1 ≤ a ≤ n) — the number of the table row, b (1 ≤ b ≤ m) — the number of the column, c — the value containing in the cell (1 or -1). They are numbered starting from 1. It is guaranteed that no two lines with same a and b values exist. The last line contains an integer p (2 ≤ p ≤ 109 + 7).

第一行包含两个整数 $n$ 和 $m$（$1 \leq n, m \leq 1000$）。
第二行包含整数 $k$（$0 \leq k < \max(n, m)$）—— 表示数据被保留的单元格数量。
接下来的 $k$ 行描述了这些被保留单元格中表格的状态。每行格式为 “$a$ $b$ $c$”，其中 $a$（$1 \leq a \leq n$）表示表格的行号，$b$（$1 \leq b \leq m$）表示列号，$c$ 表示该单元格中的值（为 $1$ 或 $-1$）。行列编号均从 $1$ 开始。保证不存在两行具有相同的 $a$ 和 $b$ 值。
最后一行包含一个整数 $p$（$2 \leq p \leq 10^9 + 7$）。

Print the number of different tables that could conform to the preserved data modulo p.

输出符合保留数据的不同表格的数量对 $p$ 取模的结果。