你非常喜欢吃意面，每天晚餐都会自己做意面吃。你会做番茄酱、奶油酱和罗勒酱这 $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$。