Snuke spielt mit dem folgenden Spielstein (dieser Spielstein wird in einem Spiel namens TRAX verwendet):

Snuke möchte ein $H \times W$ großes Gitter mit diesen Spielsteinen füllen. In jede Zelle des Gitters legt er einen Spielstein in einer der vier Ausrichtungen:

Diese Ausrichtungen sind wie im obigen Bild mit 1 bis 4 nummeriert.

Die Anordnung der Spielsteine muss die folgenden Bedingungen erfüllen:

• Ein roter Bogen darf keinen weißen Bogen berühren.
• Das Gitter darf keine geschlossenen Kreise enthalten (siehe die Beispiele unten).
• Für jedes $i$ mit $1 \le i \le N$ muss der Spielstein in der Zelle, die von oben gezählt in der $R_i$-ten Zeile und von links gezählt in der $C_i$-ten Spalte liegt, die Ausrichtung $D_i$ haben.

Das folgende Bild zeigt beispielsweise zwei ungültige Anordnungen von Spielsteinen. Die linke Anordnung enthält einen weißen geschlossenen Kreis, und die rechte Anordnung enthält einen roten geschlossenen Kreis und einen großen weißen geschlossenen Kreis.

Bestimme die Anzahl gültiger Anordnungen modulo $10^9+7$.

Eingabe

$$ \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$
• Die Paare $(R_i,C_i)$ sind paarweise verschieden.

Ausgabe

Gib die Anzahl gültiger Anordnungen modulo $10^9+7$ aus.

Beispiele

Eingabe 1

2 2
1
1 1 4

Ausgabe 1

4

Eingabe 2

2 10
2
1 1 1
1 2 1

Ausgabe 2

0

Eingabe 3

2015 1114
0

Ausgabe 3

711460824

Eingabe 4

2 2
2
1 1 1
2 2 3

Ausgabe 4

0

Eingabe 5

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

Ausgabe 5

12

Eingabe 6

5 6
2
3 3 4
3 4 2

Ausgabe 6

39

Hinweis

Dies sind die vier gültigen Anordnungen für Beispiel 1: