ZHY 的矩阵

温馨提示：本题不允许套取数据。

ZHY 的记忆中有一个 $k$ 行 $n$ 列的 01 矩阵 $A$，满足下列条件： - 每一列都至多有一个 $1$。 - 每行相邻的两个 $1$ 所在的两列夹出的 $k$ 行的矩形（包括这两列）内至少有三个 $1$。 突然，ZHY 想起来了矩阵中 $x$ 个位置的值。请你计算有多少种填充 $A$ 的剩余位置的方案，使得 $A$ 满足条件。 ---- 形式化的讲，设 $A$ 第 $i$ 行第 $j$ 列的数为 $A_{i,j}$，则 $A$ 满足下列条件： - 对于 $\forall i \in [1,k],\kern{2pt}j \in [1,n]$，$A_{i,j} \in \{0,1\}$。 - 对于 $\forall i \in [1,n]$，$\displaystyle\sum_{j=1}^{k} A_{j,i}\le 1$。 - 对于 $\forall i,j \in [1,n],\kern{2pt}p \in [1,k]$ 且 $j>i$，若有 $A_{p,i}=A_{p,j}=1,\displaystyle \sum_{x=i}^{j}A_{p,x}=2$，则有 $\Big(\displaystyle \sum_{x=1}^{k} \sum_{y=i}^{j} A_{x,y}\Big) \ge 3$。 - 对于 $\forall i\in[1,x]$，有 $A_{a_{i},b_{i}}=c_{i}$。 由于答案可能很大，你只需告诉 ZHY 答案对 $10^{9}+7$ 取模的结果。定义两个矩阵 $A,A'$ 不同，当且仅当存在 $i\in[1,k]$，$j\in[1,n]$ 满足 $A_{i,j}\ne A'_{i,j}$。

第一行三个整数，表示 $n,k,x$。 接下来 $x$ 行，每行三个整数 $a_{i},b_{i},c_{i}$。

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

3 2 2
1 1 1
2 2 0

2

**样例解释** 满足条件的矩阵只有以下 $2$ 种： $$ \begin{Bmatrix} 1&0&0\\ 0&0&0 \end{Bmatrix} $$ $$ \begin{Bmatrix} 1&0&0\\ 0&0&1 \end{Bmatrix} $$ ---- **本题采用捆绑测试。** | $\mathrm{Subtask} \kern{2pt} \mathrm{id}$ | $n$ | $x$ | 特殊性质 | 分值 | | :-----: | :-----: | :-----: | :-----: | :-----: | | $0$ | $\le 8$ | $\le 8$ | $k=2$ | $12$ | | $1$ | $\le 2 \times 10^{5}$ | $\le 2\times 10^{5}$ | 无 | $26$ | | $2$ | $\le 10^{9}$ | $=0$ | 无 | $23$ | | $3$ | $\le 10^{9}$ | $\le 2\times 10^{5}$ | $c_{i}=1$ | $15$ | | $4$ | $\le 10^{9}$ | $\le 2\times 10^{5}$ | 无 | $24$ | 对于所有数据，$1 \le n \le 10^{9}$，$0 \le x \le 2\times 10^{5}$，$2\le k \le 100$。$1 \le a_{i} \le k$，$1 \le b_{i} \le n$，$c_{i} \in \{0,1\}$。保证不存在一对 $i,j \in [1,x],\kern{2pt}i\neq j$，满足 $a_{i}=a_{j},\kern{2pt}b_{i}=b_{j}$。