Snuke играет со следующей фишкой (такая фишка используется в игре под названием TRAX):

Snuke хочет заполнить такими фишками сетку размером $H \times W$. В каждую клетку сетки он кладёт фишку в одной из четырёх ориентаций:

Эти ориентации пронумерованы от 1 до 4, как показано на рисунке выше.

Расстановка фишек должна удовлетворять следующим ограничениям:

• Красная дуга не должна соприкасаться с белой дугой.
• Сетка не должна содержать циклов (см. примеры ниже).
• Для каждого $i$ ($1 \le i \le N$) в клетке, находящейся в $R_i$-й строке сверху и $C_i$-м столбце слева, ориентация фишки должна быть $D_i$.

Например, на следующем рисунке показаны две недопустимые расстановки фишек. Левая расстановка содержит белый цикл, а правая содержит красный цикл и большой белый цикл.

Подсчитайте количество допустимых расстановок по модулю $10^9+7$.

Входные данные

$$ \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$
• Пары $(R_i,C_i)$ попарно различны.

Выходные данные

Выведите количество допустимых расстановок по модулю $10^9+7$.

Примеры

Входные данные 1

2 2
1
1 1 4

Выходные данные 1

4

Входные данные 2

2 10
2
1 1 1
1 2 1

Выходные данные 2

0

Входные данные 3

2015 1114
0

Выходные данные 3

711460824

Входные данные 4

2 2
2
1 1 1
2 2 3

Выходные данные 4

0

Входные данные 5

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

Выходные данные 5

12

Входные данные 6

5 6
2
3 3 4
3 4 2

Выходные данные 6

39

Примечание

Для примера 1 существуют следующие четыре допустимые расстановки: