Matrix Filling with Gap Constraint

ZHY has a memory of a binary matrix \(A\) with \(k\) rows and \(n\) columns satisfying the following conditions:

• Each column contains at most one \(1\).
• For every row, if there are two \(1\)s that are consecutive in that row (i.e. no other \(1\) in that row appears between them), then the \(k\times (j-i+1)\) submatrix spanning from column \(i\) to column \(j\) (including these two columns) must have a total sum of at least \(3\). In other words, if in some row \(p\) we have \(A_{p,i}=A_{p,j}=1\) and \(\sum_{x=i}^{j}A_{p,x}=2\), then it must hold that \[ \sum_{x=1}^{k}\sum_{y=i}^{j}A_{x,y} \ge 3. \]

Moreover, ZHY remembers the values of \(x\) specific positions in the matrix. Formally, for \(i=1,2,\dots,x\) we have a predetermined cell \(A_{a_i,b_i}=c_i\) where \(c_i\in \{0,1\}\).

Your task is to count the number of ways to fill the remaining positions of \(A\) so that all conditions are satisfied. As the answer can be very large, output it modulo \(10^9+7\).

Note: Two matrices \(A\) and \(A'\) are considered different if there exists some \(i\in[1,k]\) and \(j\in[1,n]\) such that \(A_{i,j}\neq A'_{i,j}\).

inputFormat

The first line contains three integers \(k\), \(n\) and \(x\) \( (1\le k,n\le ?;\, 0\le x\le k\times n)\). Each of the next \(x\) lines contains three integers \(a_i\), \(b_i\) and \(c_i\) indicating that the cell at row \(a_i\) and column \(b_i\) is fixed to \(c_i\) (either \(0\) or \(1\)).

It is guaranteed that the predetermined values do not conflict with the rule that every column can have at most one \(1\).

outputFormat

Output a single integer: the number of ways to complete the matrix modulo \(10^9+7\).

sample

1 3 0

4