Bạn rất thích mì Ý và ngày nào cũng tự nấu mì Ý cho bữa tối. Bạn biết làm ba loại mì Ý: sốt cà chua, sốt kem và sốt húng quế.

Bạn quyết định lên thực đơn bữa tối cho \(N\) ngày. Mỗi ngày, bạn chọn một trong ba loại mì Ý. Tuy nhiên, ăn cùng một loại liên tục sẽ gây chán, nên không được chọn cùng một loại mì Ý trong ba ngày liên tiếp trở lên. Ngoài ra, loại mì Ý của \(K\) ngày trong số \(N\) ngày đã được quyết định trước.

Yêu cầu

Cho \(N\) và thông tin về \(K\) ngày đã quyết định, hãy đếm số thực đơn thỏa mãn các điều kiện trên và lấy phần dư khi chia cho \(10000\).

Dữ liệu vào

Dữ liệu vào gồm \(K+1\) dòng.

Dòng đầu tiên chứa hai số nguyên \(N\), \(K\), cách nhau bởi dấu cách.

Dòng thứ \(1+i\), với \(1 \le i \le K\), chứa hai số nguyên \(A_i\), \(B_i\), cách nhau bởi dấu cách. Điều này có nghĩa là loại mì Ý của ngày thứ \(A_i\) đã được quyết định:

• \(B_i=1\): sốt cà chua.
• \(B_i=2\): sốt kem.
• \(B_i=3\): sốt húng quế.

Dữ liệu ra

In ra một dòng chứa phần dư khi chia số thực đơn hợp lệ cho \(10000\).

Ràng buộc

• \(3 \le N \le 100\).
• \(1 \le K \le N\).
• \(1 \le A_i \le N\) và \(1 \le B_i \le 3\), với \(1 \le i \le K\).
• Các giá trị \(A_1,A_2,\ldots,A_K\) đôi một khác nhau.
• Dữ liệu bảo đảm có ít nhất một thực đơn hợp lệ.
• Mọi giá trị trong dữ liệu vào đều là số nguyên.

Ví dụ

5 3
3 1
1 1
4 2

6

20 5
10 2
4 3
12 1
13 2
9 1

2640