← 返回题目列表

AtCoder · agc017_f

F. 之字形

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

分数: 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