Sam và em gái Sara có một bảng gồm \(n \times m\) ô vuông. Hai anh em muốn tô mỗi ô bằng màu đỏ hoặc xanh sao cho mọi hình vuông \(2 \times 2\) gồm các ô kề nhau đều chứa một số lẻ ô đỏ, tức là \(1\) hoặc \(3\) ô.

Ví dụ, bảng \(3 \times 5\) sau là một cách tô hợp lệ.

Đêm qua, ai đó đã tô sẵn một số ô màu đỏ và một số ô màu xanh. Sam và Sara muốn biết có thể tô các ô còn lại theo quy tắc trên hay không, và có bao nhiêu cách tô như vậy. Không được thay đổi màu của các ô đã tô sẵn.

Dữ liệu vào

Dòng đầu chứa ba số nguyên \(n\), \(m\), \(k\), lần lượt là số hàng, số cột và số ô đã được tô sẵn.

Trong \(k\) dòng tiếp theo, dòng thứ \(i\) chứa ba số nguyên \(x_i\), \(y_i\), \(c_i\): hàng, cột và màu của ô đã tô thứ \(i\). Giá trị \(c_i=1\) biểu thị màu đỏ, còn \(c_i=0\) biểu thị màu xanh. Các ô được mô tả có vị trí đôi một khác nhau.

Dữ liệu ra

In một số nguyên trên một dòng: số cách tô hợp lệ lấy phần dư khi chia cho \(10^9\). Nếu không có cách tô hợp lệ, in \(0\).

Ràng buộc

• \(2 \le n,m \le 10^5\).
• \(0 \le k \le 10^5\).
• \(1 \le x_i \le n\), \(1 \le y_i \le m\), \(c_i \in \{0,1\}\) với mọi \(1 \le i \le k\).

Phân nhóm

Mỗi phân nhóm được chấm độc lập theo kiểu tất cả hoặc không: bạn chỉ nhận điểm của nhóm khi đúng toàn bộ test trong nhóm. Điểm trong bảng là phần điểm cộng thêm trên LQDOJ; nhóm sau bao gồm lại các test thỏa điều kiện của nhóm trước.

Ví dụ

3 4 3
2 2 1
1 2 0
2 3 1

8

Nguồn

APIO 2011 — Table Coloring.