问题

你非常喜欢意大利面，每天晚餐都会做意大利面吃。你会做三种面食：番茄酱面、奶油面和罗勒酱面。

现在你考虑了连续 $N$ 天的晚餐计划。每天从这三种面食中选择一种。然而，由于吃同样的面食会变得乏味，所以不能连续 $3$ 天选择同一种面食。另外，有 $K$ 天的晚餐已经确定了。

给定 $N$ 和已确定晚餐的 $K$ 以及它们的信息，请编写程序计算满足条件的晚餐计划有多少种，结果对 $10,000$ 取余。

输入

输入共 $K+1$ 行。

第 $1$ 行包含两个整数 $N$ 和 $K$ ($3 \leq N \leq 100$, $1 \leq K \leq N$)。

接下来 $K$ 行，每行包含两个整数 $A_i$ 和 $B_i$ ($1 \leq A_i \leq N$, $1 \leq B_i \leq 3$)。表示 $A_i$ 天的晚餐已经确定，其中 $B_i = 1$ 表示番茄酱面，$B_i = 2$ 表示奶油面，$B_i = 3$ 表示罗勒酱面。所有的 $A_i$ ($1 \leq i \leq K$) 都是不同的。输入数据保证存在至少 $1$ 种满足条件的晚餐计划。

输出

输出满足条件的晚餐计划的数量对 $10,000$ 取余后的结果。

示例 1

5 3
3 1
1 1
4 2

输出 1

6

在示例 1 中，你考虑了连续 $5$ 天的晚餐计划。第 $1$ 天和第 $3$ 天选择番茄酱面，第 $4$ 天选择奶油面。根据条件的限制，共有 $6$ 种满足条件的晚餐计划。

这个表中，$1$ 表示番茄酱面，$2$ 表示奶油面，$3$ 表示罗勒酱面。

示例 2

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

输出 2

2640

在示例 2 中，满足条件的晚餐计划共有 $4,112,640$ 种。取余 $10,000$ 得到结果 $2,640$。