Problem Description

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}$.

Input Format

The first line contains three integers $n,k,x$.

The next $x$ lines each contain three integers $a_{i},b_{i},c_{i}$.

Output Format

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

3 2 2
1 1 1
2 2 0

2

Hint

Sample Explanation

There are only the following $2$ matrices that satisfy the conditions:

This problem uses bundled testdata.

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