格子衫染色机

题目信息

时间限制: 1s

空间限制: 256M

输入文件: d.in

输出文件: d.out

题目描述

毕业于 T 学校 Arts & Design 学院的 D 酱在本科期间辅修了计算机专业，这段独特的经历使得 D 酱的创业项目“红蓝格子衫”迅速在 CN 国的程序员中流行起来。“红蓝格子衫”的原材料是可以分成 $(n-1)\times (m-1)$ 个方格的网格布，这块大网格布上的 $n\times m$ 个交叉点都要染成红色或蓝色。D 酱捕获程序员芳心的秘诀是：如果网格布上任意一个方格的四个顶点中，恰好有 $k$ 个点是一种颜色，而另 $4-k$ 个点是另一种颜色，那么这块网格布裁出的任何一件衣服都是优质“红蓝格子衫”。

D 酱通过在“红蓝格子衫”爆火后的市场调研报告中发现，如果网格布中恰好 $r$ 个交点染上了指定颜色，那么这块网格布裁出的“红蓝格子衫”的销量就能更上一层楼。

D 酱进一步发明了格子衫染色机，因为 D 酱想要知道符合上述限制的条件下，能染色出多少种不同的网格布。因为染色方案非常多，所以格子衫染色机的输出总是对 $P=10^9+7$ 取模。

输入格式

第一行：四个非负整数 $n, m, k, r$ 。

接下来 $r$ 行: 每行三个正整数 $x, y, z$ ，表示指定的坐标和颜色。其中 $z=0$ 为红色， $z=1$ 为蓝色。

输出格式

一行一个非负整数，表示答案。

样例

样例输入 1

142857 7 0 6
100000 1 0
10000 2 0
1000 3 0
100 4 0 
10 5 0 
1 6 0

样例输出 1

样例解释 1

只能全部染红。

样例输入 2

142857 1919810 1 10
100000 1 0
19198 114514 0
10000 1 1
19198 114515 1
1000 1 1
19199 114514 1
100 1 0
19199 114515 1
10 1 0
1 1 1

样例输出 2

399886627

样例输入 3

样例输出 3

数据范围与提示

对于 $100 \%$ 的数据， $2 \leq n, m \leq 10^9, 0 \leq k \leq 2,0 \leq r \leq 10^5$ 。

保证 $1 \leq x \leq n, 1 \leq y \leq m, 0 \leq z \leq 1$ ，且所有指定坐标各不相同。

Subtask 1 (20 pts): $k \cdot r=0$ ;
Subtask 2 (30 pts): $n, m \leq 10$ ;
Subtask 3 (50 pts): 无特殊限制。