分数: 1600 点
问题陈述
有 N(N+1)/2 点排列成一个等边三角形,其边由 N 点,如下图。 的 j- 从左边算起的第一个点 i从顶部开始的第行表示为 (i, j) (1 \leq i \leq N, 1 \leq j \leq i)。 另外,我们会打电话 (i+1, j) 立即左下角 (i, j),和 (i+1, j+1) 立即右下角 (i, j).

高桥正在画画 M 折线 L_1, L_2, ..., L_M 连接这些点。 每个 L_i 开始于 (1, 1),并访问当前点的左下或右下紧邻的点 N-1 次。 更正式地说,存在 X_{i,1}, ..., X_{i,N} 这样:
- L_i 连接 N 点 (1, X_{i,1}), (2, X_{i,2}), ..., (N, X_{i,N}),按此顺序。
- 对于每个 j=1, 2, ..., N-1,或者 X_{i,j+1} = X_{i,j} or X_{i,j+1} = X_{i,j}+1 成立。
高桥想画出这些线,以便没有任何一部分 L_{i+1} 位于左侧 L_{i}。 也就是说,对于每个 j=1, 2, ..., N, X_{1,j} \leq X_{2,j} \leq ... \leq X_{M,j} 必须保留。
此外,还有 K 必须遵循的线条形状条件。 的 i-第条件表示为 (A_i, B_i, C_i),这意味着:
- If C_i=0, L_{A_i} 必须访问紧邻左下角的点 B_i第一步。
- If C_i=1, L_{A_i} 必须访问紧邻右下角的点 B_i第一步。
也就是说, X_{A_i, {B_i}+1} = X_{A_i, B_i} + C_i 必须保留。
高桥有多少种画法 M 折线?求计数模数 1000000007.
注释
在提交之前,强烈建议使用“自定义测试”来测量代码的执行时间。
约束
- 1 \leq N \leq 20
- 1 \leq M \leq 20
- 0 \leq K \leq (N-1)M
- 1 \leq A_i \leq M
- 1 \leq B_i \leq N-1
- C_i = 0 or 1
- 没有任何对出现超过一次 (A_i, B_i).
输入
输入由标准输入按以下格式给出:
N M K A_1 B_1 C_1 A_2 B_2 C_2 : A_K B_K C_K
输出
打印高桥绘制的方式数 M 折线,模 1000000007.
样本输入 1
3 2 1 1 2 0
示例输出 1
6
画线有六种方法,如下所示。这里,红线代表 L_1,绿线代表 L_2.

示例输入 2
3 2 2 1 1 1 2 1 0
示例输出 2
0
示例输入 3
5 4 2 1 3 1 4 2 0
示例输出 3
172
示例输入 4
20 20 0
示例输出 4
881396682