Snuke joue avec la tuile suivante (cette tuile est utilisée dans un jeu appelé TRAX) :

Snuke souhaite remplir une grille de $H \times W$ cases avec ces tuiles. Dans chaque case de la grille, il place une tuile dans l'une des quatre orientations suivantes :

Ces orientations sont numérotées de $1$ à $4$, comme sur l'image ci-dessus.

La disposition des tuiles doit respecter les contraintes suivantes :

• Un arc rouge ne doit pas toucher un arc blanc.
• La grille ne doit contenir aucun cycle (voir les exemples ci-dessous).
• Pour chaque $i$ ($1 \le i \le N$), dans la case située à la $R_i$-ième ligne depuis le haut et à la $C_i$-ième colonne depuis la gauche, l'orientation de la tuile doit être $D_i$.

Par exemple, l'image suivante montre deux dispositions de tuiles non valides. La disposition de gauche contient un cycle blanc, et celle de droite contient un cycle rouge et un grand cycle blanc.

Comptez le nombre de dispositions valides, modulo $10^9 + 7$.

Entrée

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

• $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$
• Les couples $(R_i, C_i)$ sont deux à deux distincts.

Sortie

Affichez le nombre de dispositions valides, modulo $10^9 + 7$.

Exemples

Entrée 1

2 2
1
1 1 4

Sortie 1

4

Entrée 2

2 10
2
1 1 1
1 2 1

Sortie 2

0

Entrée 3

2015 1114
0

Sortie 3

711460824

Entrée 4

2 2
2
1 1 1
2 2 3

Sortie 4

0

Entrée 5

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

Sortie 5

12

Entrée 6

5 6
2
3 3 4
3 4 2

Sortie 6

39

Remarque

Voici les quatre dispositions valides pour l'exemple $1$ :