Snuke bawi się następującym kafelkiem (kafelek ten jest używany w grze o nazwie TRAX):

Snuke chce wypełnić tymi kafelkami siatkę $H \times W$. W każdej komórce siatki umieszcza kafelek w jednej z czterech orientacji:

Orientacje te są ponumerowane od 1 do 4, jak na powyższym rysunku.

Rozmieszczenie kafelków musi spełniać następujące warunki:

• Czerwony łuk nie może stykać się z białym łukiem.
• Siatka nie może zawierać cykli (zobacz przykłady poniżej).
• Dla każdego $i$ ($1 \le i \le N$) kafelek w komórce w $R_i$-tym wierszu od góry i $C_i$-tej kolumnie od lewej musi mieć orientację $D_i$.

Na przykład poniższy rysunek przedstawia dwa niepoprawne rozmieszczenia kafelków. Rozmieszczenie po lewej zawiera biały cykl, a rozmieszczenie po prawej zawiera czerwony cykl i duży biały cykl.

Oblicz liczbę poprawnych rozmieszczeń modulo $10^9 + 7$.

Wejście

$$ \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$
• Pary $(R_i, C_i)$ są parami różne.

Wyjście

Wypisz liczbę poprawnych rozmieszczeń modulo $10^9 + 7$.

Przykład

Wejście 1

2 2
1
1 1 4

Wyjście 1

4

Wejście 2

2 10
2
1 1 1
1 2 1

Wyjście 2

0

Wejście 3

2015 1114
0

Wyjście 3

711460824

Wejście 4

2 2
2
1 1 1
2 2 3

Wyjście 4

0

Wejście 5

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

Wyjście 5

12

Wejście 6

5 6
2
3 3 4
3 4 2

Wyjście 6

39

Uwagi

Dla przykładu 1 są to cztery poprawne rozmieszczenia: