Bạn là một tín đồ của món pasta và thưởng thức nó mỗi ngày cho bữa tối. Bạn có thể làm 3 loại pasta khác nhau: sốt cà chua, sốt kem và sốt húng quế.

Bạn đang lên kế hoạch thực đơn cho bữa tối trong N ngày. Mỗi ngày, bạn cần chọn một trong ba loại pasta. Tuy nhiên, bạn không muốn ăn cùng một loại pasta liên tiếp trong hơn 3 ngày, để tránh cảm giác nhàm chán. Đồng thời, trong số N ngày, có K ngày đã được xác định trước loại pasta sẽ ăn.

Khi được cung cấp giá trị N và thông tin về K ngày đã xác định, hãy viết một chương trình để tính số lượng kế hoạch thực đơn thỏa mãn điều kiện đã cho, sau đó in ra số dư của kết quả khi chia cho 10000.

• Dòng đầu tiên chứa hai số nguyên N và K (3 ≤ N ≤ 100, 1 ≤ K ≤ N), tương ứng là số ngày và số ngày đã được xác định.
• K dòng tiếp theo, mỗi dòng chứa hai số nguyên A_i và B_i (1 ≤ A_i ≤ N, 1 ≤ B_i ≤ 3). Đây là thông tin cho biết vào ngày thứ A_i, bạn đã chọn món pasta loại B_i: 1 cho sốt cà chua, 2 cho sốt kem và 3 cho sốt húng quế. Các giá trị A_i là khác nhau.

In ra số lượng kế hoạch thực đơn thỏa mãn điều kiện chia cho 10000.

Giải thích: Bạn cần lên kế hoạch cho 5 ngày, với món pasta đã xác định là:

• Ngày 1: sốt cà chua
• Ngày 3: sốt cà chua
• Ngày 4: sốt kem

Các kế hoạch thực đơn hợp lệ có thể là:

1 2 1 2 1
1 2 1 2 2
1 2 1 2 3
1 3 1 2 1
1 3 1 2 2
1 3 1 2 3