最近发现,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