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 ต่อไปนี้คือวิธีวางที่ถูกต้องทั้งสี่แบบ: