P9490 ZHY's Matrix

In ZHY's memory, there is a $0$-$1$ matrix $A$ with $k$ rows and $n$ columns, which satisfies the following conditions: - Each column contains at most one $1$. - For any two adjacent $1$'s in the same row, within the rectangle of $k$ rows between the two columns (including these two columns), there are at least three $1$'s in total. Suddenly, ZHY recalled the values of $x$ positions in the matrix. Please calculate how many ways there are to fill the remaining positions of $A$ so that $A$ satisfies the conditions. ---- Formally, let the value in row $i$ and column $j$ be $A_{i,j}$. Then $A$ satisfies: - For all $\forall i \in [1,k],\kern{2pt}j \in [1,n]$, $A_{i,j} \in \{0,1\}$. - For all $\forall i \in [1,n]$, $\displaystyle\sum_{j=1}^{k} A_{j,i}\le 1$. - For all $\forall i,j \in [1,n],\kern{2pt}p \in [1,k]$ and $j>i$, if $A_{p,i}=A_{p,j}=1,\displaystyle \sum_{x=i}^{j}A_{p,x}=2$, then $\Big(\displaystyle \sum_{x=1}^{k} \sum_{y=i}^{j} A_{x,y}\Big) \ge 3$. - For all $\forall i\in[1,x]$, $A_{a_{i},b_{i}}=c_{i}$. Since the answer may be very large, you only need to output the result modulo $10^{9}+7$. Define that two matrices $A,A'$ are different if and only if there exist $i\in[1,k]$, $j\in[1,n]$ such that $A_{i,j}\ne A'_{i,j}$.

The first line contains three integers $n,k,x$. The next $x$ lines each contain three integers $a_{i},b_{i},c_{i}$.

Output one integer in a single line, representing the answer.

**Sample Explanation** There are only the following $2$ matrices that satisfy the conditions: $$ \begin{Bmatrix} 1&0&0\\ 0&0&0 \end{Bmatrix} $$ $$ \begin{Bmatrix} 1&0&0\\ 0&0&1 \end{Bmatrix} $$ ---- **This problem uses bundled testdata.** | $\mathrm{Subtask} \kern{2pt} \mathrm{id}$ | $n$ | $x$ | Special Properties | Score | | :-----: | :-----: | :-----: | :-----: | :-----: | | $0$ | $\le 8$ | $\le 8$ | $k=2$ | $12$ | | $1$ | $\le 2 \times 10^{5}$ | $\le 2\times 10^{5}$ | None | $26$ | | $2$ | $\le 10^{9}$ | $=0$ | None | $23$ | | $3$ | $\le 10^{9}$ | $\le 2\times 10^{5}$ | $c_{i}=1$ | $15$ | | $4$ | $\le 10^{9}$ | $\le 2\times 10^{5}$ | None | $24$ | Constraints: for all testdata, $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\}$. It is guaranteed that there do not exist $i,j \in [1,x],\kern{2pt}i\neq j$ such that $a_{i}=a_{j},\kern{2pt}b_{i}=b_{j}$. Translated by ChatGPT 5