← 返回题目列表

Codeforces · 40/E

E. 号码表

中文机器翻译题面 查看原题

最近发现,Berland当前的所有经济状况都可以用一张n×m大小的简单表格来描述。 n — Berland 每个月的天数,m — 月数。因此,表格单元格对应于 Berland 年的一天和一个月。每个单元格将包含 1 或 -1,这意味着该州在特定月份、特定日期的收益。 1对应于利润,-1对应于损失。事实证明,分析上一年的经济状况数据对于成功开发非常重要,但当财务主管查阅档案检索数据时,发现表格已严重损坏。在某些表格单元格中,数值已经褪色并且无法破译。已知保存数据的单元格数量严格小于 max(n, m)。然而,还有额外的信息——每行和每列中的数字的乘积等于-1。您的任务是找出有多少个不同的表可能符合保留的数据。由于任务的答案可能非常大,因此您必须对 p 求模。

输入

第一行包含整数 n 和 m (1 ≤ n, m ≤ 1000)。第二行包含整数 k (0 ≤ k < max(n, m)) — 保存数据的单元格数量。接下来的 k 行包含有关保留单元格中表状态的数据。每行的形式为“a b c”,其中 a (1 ≤ a ≤ n) — 表格行号,b (1 ≤ b ≤ m) — 列号,c — 单元格中包含的值(1 或 -1)。它们从1开始编号。保证不存在具有相同a和b值的两行。最后一行包含一个整数 p (2 ≤ p ≤ 109 + 7)。

输出

打印符合保留数据模 p 的不同表的数量。

示例

输入 #1

2 2
0
100

输出 #1

2

输入 #2

2 2
1
1 1 -1
100

输出 #2

1