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\ W\\ N\\ R_1\ C_1\ D_1\\ \vdots\\ R_N\ C_N\ 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, אלה הן ארבע ההנחות התקינות: