Score : 1600 points
There are N(N+1)/2 dots arranged to form an equilateral triangle whose sides consist of N dots, as shown below. The j-th dot from the left in the i-th row from the top is denoted by (i, j) (1 \leq i \leq N, 1 \leq j \leq i). Also, we will call (i+1, j) immediately lower-left to (i, j), and (i+1, j+1) immediately lower-right to (i, j).
Takahashi is drawing M polygonal lines L_1, L_2, ..., L_M by connecting these dots. Each L_i starts at (1, 1), and visits the dot that is immediately lower-left or lower-right to the current dots N-1 times. More formally, there exist X_{i,1}, ..., X_{i,N} such that:
Takahashi would like to draw these lines so that no part of L_{i+1} is to the left of L_{i}. That is, for each j=1, 2, ..., N, X_{1,j} \leq X_{2,j} \leq ... \leq X_{M,j} must hold.
Additionally, there are K conditions on the shape of the lines that must be followed. The i-th condition is denoted by (A_i, B_i, C_i), which means:
That is, X_{A_i, {B_i}+1} = X_{A_i, B_i} + C_i must hold.
In how many ways can Takahashi draw M polygonal lines? Find the count modulo 1000000007.
Before submission, it is strongly recommended to measure the execution time of your code using "Custom Test".
Input is given from Standard Input in the following format:
N M K A_1 B_1 C_1 A_2 B_2 C_2 : A_K B_K C_K
Print the number of ways for Takahashi to draw M polygonal lines, modulo 1000000007.
3 2 1 1 2 0
6
There are six ways to draw lines, as shown below. Here, red lines represent L_1, and green lines represent L_2.
3 2 2 1 1 1 2 1 0
0
5 4 2 1 3 1 4 2 0
172
20 20 0
881396682