Snuke chơi với mảnh ghép sau (mảnh ghép này được dùng trong trò chơi có tên TRAX):

Snuke muốn lấp đầy một bảng ô vuông kích thước $H \times W$ bằng các mảnh ghép này. Trong mỗi ô của bảng, cậu đặt một mảnh ghép theo một trong bốn hướng:

Các hướng này được đánh số từ $1$ đến $4$ như trong hình trên.

Cách đặt các mảnh ghép phải thỏa mãn những điều kiện sau:

• Một cung màu đỏ không được chạm vào một cung màu trắng.
• Bảng không được chứa chu trình (xem các ví dụ bên dưới).
• Với mỗi $i$ ($1 \le i \le N$), tại ô ở hàng thứ $R_i$ tính từ trên xuống và cột thứ $C_i$ tính từ trái sang, hướng của mảnh ghép phải là $D_i$.

Chẳng hạn, hình sau minh họa hai cách đặt các mảnh ghép không hợp lệ. Cách đặt bên trái chứa một chu trình màu trắng, còn cách đặt bên phải chứa một chu trình màu đỏ và một chu trình lớn màu trắng.

Hãy đếm số cách đặt hợp lệ, lấy phần dư khi chia cho $10^9 + 7$.

Dữ liệu vào

$$ \begin{aligned} &H\quad W\\ &N\\ &R_1\quad C_1\quad D_1\\ &\vdots\\ &R_N\quad C_N\quad D_N \end{aligned} $$

• $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$
• Các cặp $(R_i, C_i)$ đôi một khác nhau.

Dữ liệu ra

In ra số cách đặt hợp lệ, lấy phần dư khi chia cho $10^9 + 7$.

Ví dụ

Dữ liệu vào 1

2 2
1
1 1 4

Dữ liệu ra 1

4

Dữ liệu vào 2

2 10
2
1 1 1
1 2 1

Dữ liệu ra 2

0

Dữ liệu vào 3

2015 1114
0

Dữ liệu ra 3

711460824

Dữ liệu vào 4

2 2
2
1 1 1
2 2 3

Dữ liệu ra 4

0

Dữ liệu vào 5

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

Dữ liệu ra 5

12

Dữ liệu vào 6

5 6
2
3 3 4
3 4 2

Dữ liệu ra 6

39

Ghi chú

Trong ví dụ 1, đây là bốn cách đặt hợp lệ: