Snuke plays with the following tile (this tile is used in a game called TRAX):

Snuke wants to fill an $H \times W$ grid with these tiles. In each cell of the grid, he places a tile in one of the four orientations:

These orientations are numbered 1 through 4 as in the picture above.

The placement of tiles must satisfy the following constraints:

• A red arc must not touch a white arc.
• The grid must not contain cycles (see the examples below).
• For each $i$ ($1 \le i \le N$), in the cell that is $R_i$-th from the top and $C_i$-th from the left, the orientation of the tile must be $D_i$.

For example, the following picture shows two invalid placements of tiles. The placement on the left contains a white cycle, and the placement on the right contains a red cycle and a white large cycle.

Count the number of valid placements, modulo $10^9 + 7$.

Input

$$ \begin{gathered} H\ W\\ N\\ R_1\ C_1\ D_1\\ \vdots\\ R_N\ C_N\ D_N \end{gathered} $$

• $1 \le H,W \le 10^5$
• $0 \le N \le 10^5$
• $1 \le R_i \le H$
• $1 \le C_i \le W$
• $1 \le D_i \le 4$
• $(R_i,C_i)$ are pairwise distinct.

Output

Print the number of valid placements, modulo $10^9 + 7$.

Examples

Input 1

2 2
1
1 1 4

Output 1

4

Input 2

2 10
2
1 1 1
1 2 1

Output 2

0

Input 3

2015 1114
0

Output 3

711460824

Input 4

2 2
2
1 1 1
2 2 3

Output 4

0

Input 5

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

Output 5

12

Input 6

5 6
2
3 3 4
3 4 2

Output 6

39

Note

For sample 1, these are the four valid placements: