Bạn rất thích ăn mì Ý và mỗi ngày đều tự nấu mì Ý cho bữa tối. Bạn có thể làm $3$ loại mì Ý: sốt cà chua, sốt kem và sốt húng quế (basil).

Bạn quyết định lên kế hoạch bữa tối cho $N$ ngày. Mỗi ngày, bạn chọn $1$ loại từ $3$ loại mì Ý. Tuy nhiên, nếu ăn liên tục cùng một loại mì Ý thì sẽ bị ngán, vì vậy không được chọn cùng một loại mì Ý trong $3$ ngày liên tiếp trở lên. Ngoài ra, món mì Ý cho $K$ ngày trong số $N$ ngày đã được quyết định trước.

Cho biết giá trị của $N$ và thông tin về món mì Ý của $K$ ngày, hãy viết chương trình tính phần dư khi chia số lượng kế hoạch thỏa mãn điều kiện cho $10000$.

Dữ liệu vào

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

Dòng thứ $1$ chứa $2$ số nguyên $N, K$ ($3 \le N \le 100$, $1 \le K \le N$) cách nhau bởi khoảng trắng.

Dòng thứ $(1 + i)$ ($1 \le i \le K$) chứa $2$ số nguyên $A_i, B_i$ ($1 \le A_i \le N$, $1 \le B_i \le 3$) cách nhau bởi khoảng trắng. Điều này có nghĩa là món mì Ý vào ngày thứ $A_i$ đã được quyết định trước: khi $B_i = 1$ là sốt cà chua, khi $B_i = 2$ là sốt kem, và khi $B_i = 3$ là sốt húng quế. Tất cả các $A_i$ ($1 \le i \le K$) đều đôi một khác nhau. Trong dữ liệu vào được cho, đảm bảo có ít nhất $1$ kế hoạch thỏa mãn điều kiện.

Kết quả

In ra trên một dòng phần dư khi chia số lượng kế hoạch thỏa mãn điều kiện cho $10000$.

Ví dụ

Ví dụ đầu vào 1

5 3
3 1
1 1
4 2

Ví dụ đầu ra 1

6

Trong Ví dụ $1$, bạn lên kế hoạch cho $5$ ngày. Ngày $1$ và ngày $3$ là sốt cà chua, ngày $4$ là sốt kem. Ngoài ra, không được chọn cùng một loại mì Ý trong $3$ ngày liên tiếp trở lên. Có $6$ kế hoạch thỏa mãn các điều kiện này.

Trong bảng này, $1$ biểu thị sốt cà chua, $2$ biểu thị sốt kem và $3$ biểu thị sốt húng quế.

Ví dụ đầu vào 2

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

Ví dụ đầu ra 2

2640

Trong Ví dụ $2$, có tổng cộng $4112640$ kế hoạch thỏa mãn điều kiện. In ra $2640$, là phần dư khi chia cho $10000$.