你好鍾意食意粉，每日晚餐都會自己煮意粉食。你識得整番茄醬、忌廉醬同羅勒醬呢 $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$。