PreVOI 2025 - Contest 2 - Bảng vuông

Xem dạng PDF

Gửi bài giải

Điểm: 55,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 1G
Input: stdin
Output: stdout

Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Pascal, PyPy, Python, Scratch

Trong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài

Cho một bảng vuông kích thước ~N \times M~, các hàng được đánh số từ ~1~ đến ~N~, các cột được đánh số từ ~1~ đến ~M~. Mỗi ô trên bảng sẽ được điền vào một trong hai giá trị ~0~ hoặc ~1~ sao cho bất kỳ bảng con kích thước ~2 \times 2~ nào cũng chứa chẵn giá trị ~1~.

Có thêm ~T~ ràng buộc yêu cầu rằng giá trị của ô nằm ở hàng ~u~ cột ~v~ phải là ~x~.

Hãy đếm xem có bao nhiêu cách điền các giá trị vào để thoả mãn tất cả điều kiện.

Input

  • Dòng đầu tiên chứa ba số nguyên ~N, M, T~ ~(1 \le N, M \le 10^9; 0 \le T \le \min(10^5, N \cdot M))~ lần lượt thể hiện số hàng của bảng, số cột của bảng và số ràng buộc thêm.

  • ~T~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~u_i, v_i, x_i~ ~(1 \le u_i \le N; 1 \le v_i \le M; 0 \le x_i \le 1)~ thể hiện một ràng buộc.

Output

Gồm một dòng duy nhất chứa một số nguyên thể hiện số cách điền giá trị thoả mãn.

Vì kết quả có thể rất lớn nên hãy ghi ra phần dư của kết quả khi chia cho ~10^9 + 9999~.

Scoring

Subtask Điểm Ràng buộc
1 ~10\%~ ~N \cdot M \le 20~.
2 ~10\%~ ~T = 0~.
3 ~10\%~ ~T = 1~.
4 ~10\%~ ~T = 2~.
5 ~20\%~ ~N \le 1000~; ~M \le 8~.
6 ~20\%~ ~N, M \le 10^5~.
7 ~20\%~ Không có giới hạn gì thêm

Sample Input 1

2 2 2
1 1 0
2 2 0

Sample Output 1

2

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.