Snuke грає з такою плиткою (ця плитка використовується у грі TRAX):

Snuke хоче заповнити сітку $H\times W$ цими плитками. У кожній клітинці сітки він розміщує плитку в одній із чотирьох орієнтацій:

Ці орієнтації пронумеровані від $1$ до $4$, як на зображенні вище.

Розміщення плиток має задовольняти такі обмеження:

• Червона дуга не повинна торкатися білої дуги.
• Сітка не повинна містити циклів (див. приклади нижче).
• Для кожного $i$ ($1\le i\le N$) у клітинці, що розташована в $R_i$-му рядку згори та $C_i$-му стовпці зліва, орієнтація плитки має бути $D_i$.

Наприклад, на зображенні нижче показано два недопустимі розміщення плиток. Ліве містить білий цикл, а праве — червоний цикл і великий білий цикл.

Порахуйте кількість допустимих розміщень за модулем $10^9+7$.

Вхідні дані

$$ H\ W\\ N\\ R_1\ C_1\ D_1\\ \vdots\\ R_N\ C_N\ D_N $$

• $1\le H,W\le10^5$
• $0\le N\le10^5$
• $1\le R_i\le H$
• $1\le C_i\le W$
• $1\le D_i\le4$
• Пари $(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 це чотири допустимі розміщення: