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~.

Yêu cầu: 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. 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~.

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 \times 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.