Nhà vật lý Matthew đang nghiên cứu điện động lực học lượng tử của một vi mạch hình chữ nhật làm từ silic. Vi mạch gồm một lưới electron rất lớn có kích thước \(N \times M\). Mỗi electron có spin dương, hướng lên, hoặc spin âm, hướng xuống, lần lượt được ký hiệu bằng + và -.

Matthew không biết spin của tất cả electron, nhưng anh đã thực hiện \(K\) phép đo. Trong phép đo thứ \(i\), anh xác định được rằng electron ở vị trí \((y_i,x_i)\) có spin \(s_i\). Anh còn biết rằng trong mỗi lưới con \(2 \times 2\), số electron có spin dương bằng số electron có spin âm. Anh muốn biết liệu có thể khôi phục trạng thái của mọi electron từ các phép đo hay không. Nếu không, anh muốn biết có bao nhiêu trạng thái có thể xảy ra phù hợp với các phép đo. Vì những lý do bí mật, anh muốn lấy kết quả theo modulo \(10^9+7\).

Hình: Marian Sigler, qua Wikimedia Commons; CC0, thuộc phạm vi công cộng.

Dữ liệu vào

Dòng đầu tiên chứa ba số nguyên \(N\), \(M\) và \(K\): chiều cao của lưới, chiều rộng của lưới và số phép đo.

Mỗi dòng trong \(K\) dòng tiếp theo chứa một ký hiệu spin \(s_i\), là + hoặc -, rồi đến hai số nguyên \(y_i\) và \(x_i\) (\(1 \le y_i \le N\), \(1 \le x_i \le M\)), là tọa độ của electron. Matthew không bao giờ đo hai lần tại cùng một vị trí.

Dữ liệu ra

In ra tổng số trạng thái hợp lệ phù hợp với các phép đo của Matthew, lấy modulo \(10^9+7\).

Ràng buộc

• \(1 \le N,M \le 10^9\).
• \(0 \le K \le 100\,000\).
• \(1 \le y_i \le N\) và \(1 \le x_i \le M\) với mọi \(1 \le i \le K\).
• \(s_i\) là + hoặc -.
• Không có hai phép đo tại cùng một vị trí.

Phân nhóm

Bạn chỉ nhận được điểm của một nhóm khi vượt qua tất cả các test trong nhóm đó. Tổng điểm là tổng điểm của các nhóm.

• Nhóm 1 (12 điểm): \(N,M \le 5\).
• Nhóm 2 (42 điểm): \(N,M \le 1\,000\).
• Nhóm 3 (46 điểm): Không có ràng buộc bổ sung.

Ví dụ

2 4 4

+ 1 1
- 1 2
+ 1 3
- 1 4

2

+-+-
+-+-

+-+-
-+-+

3 3 3

- 2 1
+ 2 3
+ 3 3

0

Nguồn

Baltic Olympiad in Informatics 2017, ngày thi thứ 2.