你非常喜歡吃義大利麵，每天晚餐都會自己做義大利麵吃。你會做番茄醬、奶油醬和羅勒醬這 $3$ 種義大利麵。
你決定制定接下來 $N$ 天的晚餐計畫。每一天，你都要從這 $3$ 種義大利麵中選擇 $1$ 種。但是，如果連續吃同一種義大利麵會膩，因此不能連續 $3$ 天或以上選擇同一種義大利麵。此外，$N$ 天中有 $K$ 天的義大利麵已經事先決定好了。
給定 $N$ 的值以及 $K$ 天的義大利麵資訊，請撰寫程式求出滿足條件的晚餐計畫共有多少種，並輸出其除以 $10000$ 的餘數。
輸入格式
輸入共 $K + 1$ 行。
第 $1$ 行包含 $2$ 個以空白分隔的整數 $N, K$ ($3 \le N \le 100$, $1 \le K \le N$)。
第 $(1 + i)$ 行 ($1 \le i \le K$) 包含 $2$ 個以空白分隔的整數 $A_i, B_i$ ($1 \le A_i \le N$, $1 \le B_i \le 3$)。這表示第 $A_i$ 天的義大利麵已經決定：當 $B_i = 1$ 時為番茄醬，當 $B_i = 2$ 時為奶油醬，當 $B_i = 3$ 時為羅勒醬。所有的 $A_i$ ($1 \le i \le K$) 皆不相同。在給定的輸入資料中，保證至少存在 $1$ 種滿足條件的計畫。
輸出格式
以單行輸出滿足條件的計畫數除以 $10000$ 的餘數。
範例
範例輸入 1
5 3 3 1 1 1 4 2
範例輸出 1
6
在範例 $1$ 中，你考慮 $5$ 天的計畫。第 $1$ 天和第 $3$ 天是番茄醬，第 $4$ 天是奶油醬。同時不能連續 $3$ 天或以上選擇同一種義大利麵。滿足這些條件的計畫共有 $6$ 種。
| 第 1 | 第 2 | 第 3 | 第 4 | 第 5 | |
|---|---|---|---|---|---|
| 計畫 1 | 1 | 2 | 1 | 2 | 1 |
| 計畫 2 | 1 | 2 | 1 | 2 | 2 |
| 計畫 3 | 1 | 2 | 1 | 2 | 3 |
| 計畫 4 | 1 | 3 | 1 | 2 | 1 |
| 計畫 5 | 1 | 3 | 1 | 2 | 2 |
| 計畫 6 | 1 | 3 | 1 | 2 | 3 |
在此表中，$1$ 表示番茄醬，$2$ 表示奶油醬，$3$ 表示羅勒醬。
範例輸入 2
20 5 10 2 4 3 12 1 13 2 9 1
範例輸出 2
2640
在範例 $2$ 中，滿足條件的計畫總共有 $4112640$ 種。輸出其除以 $10000$ 的餘數 $2640$。