Problem Description

Snuke is playing with pieces from a board game called TRAX. The pieces look like the ones shown in the figure below.

Snuke is arranging these pieces according to the following rules:

• Arrange $ H*W $ pieces in a grid of $ H $ rows and $ W $ columns, all facing up. The pieces can be oriented in any of the 4 possible directions.
• The red lines must connect to red lines of adjacent pieces, and the white lines must connect to white lines of adjacent pieces. In other words, the ends of red lines and white lines must not be adjacent.
• No loops should be formed. The figure below shows examples of loops. Neither the small loop formed by the red lines nor the large loop formed by the white lines on the right is allowed.

Snuke has already placed $ N $ pieces. The $i\ (1\ ≦\ i\ ≦\ N)$ piece was placed in the $ R_i $ row and $ C_i $ column with the orientation $ D_i $. The orientation is represented by an integer from 1 to 4, corresponding to the directions shown in the figure below.

How many ways are there to place the remaining pieces? Since the answer can be very large, output it modulo $ 10^9+7 $.

Input Format

The input is given from the standard input in the following format:

$ H $ $ W $ $ N $ $ R_1 $ $ C_1 $ $ D_1 $ $ R_2 $ $ C_2 $ $ D_2 $ : $ R_N $ $ C_N $ $ D_N $

• The first line contains two integers $H\ (1\ ≦\ H\ ≦\ 10^5)$ and $W\ (1\ ≦\ W\ ≦\ 10^5)$ separated by a space, indicating that Snuke is arranging the pieces in a grid of $ H $ rows and $ W $ columns.
• The second line contains an integer $N\ (0\ ≦\ N\ ≦\ 10^5)$, representing the number of pieces Snuke has already placed.
• The next $ N $ lines contain information about the pieces already placed. The $i\ (1\ ≦\ i\ ≦\ N)$ line contains three integers $R_i\ (1\ ≦\ R_i\ ≦\ H)$, $C_i\ (1\ ≦\ C_i\ ≦\ W)$, and $D_i\ (1\ ≦\ D_i\ ≦\ 4)$ separated by spaces, indicating that Snuke placed the piece in the $ R_i $ row and $ C_i $ column with the orientation $ D_i $. It is guaranteed that no location is given more than once, i.e., $R_p\ \neq\ R_q$ or $C_p\ \neq\ C_q$ when $p\ \neq\ q$.

Output Format

Output the number of ways to place the remaining pieces modulo $10^9+7\ (1,000,000,007)$ in one line. End the output with a newline.

Sample Input and Output

Sample Input #1

2 2
1
1 1 4

Sample Output #1

4

Sample Input #2

2 10
2
1 1 1
1 2 1

Sample Output #2

0

Sample Input #3

2015 1114
0

Sample Output #3

711460824

Sample Input #4

2 2
2
1 1 1
2 2 3

Sample Output #4

0

Sample Input #5

5 6
3
1 2 2
4 1 1
5 6 4

Sample Output #5

12

Sample Input #6

5 6
2
3 3 4
3 4 2

Sample Output #6

39

Notes/Hints

Partial Points

This problem has partial points.

• If you solve the dataset where $N\ =\ 0$, you will be awarded 90 points.
• If you solve the dataset without additional constraints, you will be awarded an additional 60 points.

Sample Explanation 1

There are 4 possible ways to arrange the pieces as shown in the figure below.

Sample Explanation 2

No matter how you arrange the pieces, it is impossible to satisfy the rules.

见题面 Input 部分

见题面 Output 部分