Snuke juega con la siguiente ficha (esta ficha se utiliza en un juego llamado TRAX):

Snuke quiere llenar una cuadrícula de $H\times W$ con estas fichas. En cada casilla de la cuadrícula coloca una ficha en una de las cuatro orientaciones:

Estas orientaciones están numeradas del 1 al 4 como se muestra en la imagen de arriba.

La colocación de las fichas debe satisfacer las siguientes restricciones:

• Un arco rojo no debe tocar un arco blanco.
• La cuadrícula no debe contener ciclos (véanse los ejemplos de abajo).
• Para cada $i$ ($1\le i\le N$), en la casilla situada en la fila $R_i$ desde arriba y la columna $C_i$ desde la izquierda, la orientación de la ficha debe ser $D_i$.

Por ejemplo, la siguiente imagen muestra dos colocaciones no válidas de fichas. La colocación de la izquierda contiene un ciclo blanco, y la de la derecha contiene un ciclo rojo y un ciclo blanco grande.

Cuenta el número de colocaciones válidas, módulo $10^9+7$.

Entrada

$$ \begin{gathered} H\quad W\\ N\\ R_1\quad C_1\quad D_1\\ \vdots\\ R_N\quad C_N\quad 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$
• Los pares $(R_i,C_i)$ son distintos dos a dos.

Salida

Imprime el número de colocaciones válidas, módulo $10^9+7$.

Ejemplos

Entrada 1

2 2
1
1 1 4

Salida 1

4

Entrada 2

2 10
2
1 1 1
1 2 1

Salida 2

0

Entrada 3

2015 1114
0

Salida 3

71460824

Entrada 4

2 2
2
1 1 1
2 2 3

Salida 4

0

Entrada 5

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

Salida 5

12

Entrada 6

5 6
2
3 3 4
3 4 2

Salida 6

39

Nota

Para el ejemplo 1, estas son las cuatro colocaciones válidas: