يلعب 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، هذه هي الترتيبات الأربعة الصالحة: