Snuke brinca com a seguinte peça (esta peça é usada num jogo chamado TRAX):

Snuke quer preencher uma grelha $H\times W$ com estas peças. Em cada célula da grelha, coloca uma peça numa das quatro orientações:

Estas orientações são numeradas de $1$ a $4$, como na imagem acima.

A disposição das peças deve satisfazer as seguintes condições:

• Um arco vermelho não pode tocar num arco branco.
• A grelha não pode conter ciclos (veja os exemplos abaixo).
• Para cada $i$ ($1\le i\le N$), na célula que está na $R_i$-ésima linha a contar de cima e na $C_i$-ésima coluna a contar da esquerda, a orientação da peça deve ser $D_i$.

Por exemplo, a imagem seguinte mostra duas disposições inválidas. A disposição da esquerda contém um ciclo branco, e a da direita contém um ciclo vermelho e um grande ciclo branco.

Conte o número de disposições válidas, módulo $10^9+7$.

Entrada

$H\quad W$

$N$

$R_1\quad C_1\quad D_1$

$\vdots$

$R_N\quad C_N\quad D_N$

• $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$
• Os pares $(R_i,C_i)$ são todos distintos entre si.

Saída

Imprima o número de disposições válidas, módulo $10^9+7$.

Exemplos

Entrada 1

2 2
1
1 1 4

Saída 1

4

Entrada 2

2 10
2
1 1 1
1 2 1

Saída 2

0

Entrada 3

2015 1114
0

Saída 3

711460824

Entrada 4

2 2
2
1 1 1
2 2 3

Saída 4

0

Entrada 5

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

Saída 5

12

Entrada 6

5 6
2
3 3 4
3 4 2

Saída 6

39

Nota

Para o exemplo 1, estas são as quatro disposições válidas: