T828698 菜单排期（menu）

餐厅准备安排接下来 $N$ 天的菜单。每天只供应一种主菜，主菜共有三种，依次编号为 $1,2,3$。 其中 $K$ 天的主菜已经确定，不能修改；其余日期可以选择任意一种主菜。为了避免菜单过于单调，不允许连续三天供应同一种主菜。连续两天相同是允许的。 请计算满足要求的菜单安排共有多少种。只要有一天供应的主菜不同，就认为两种安排不同。由于答案可能很大，请输出答案除以 $10000$ 的余数。 保证给定的已确定安排至少能补全为一种满足要求的菜单。

第一行一个整数 $T$，表示数据组数。 每组数据第一行两个整数 $N,K$。 接下来 $K$ 行，每行两个整数 $A_i,B_i$，表示第 $A_i$ 天已经确定供应第 $B_i$ 种主菜。所有 $A_i$ 互不相同，但不保证按日期从小到大给出。

每组数据输出一行一个整数，表示满足要求的安排数对 $10000$ 取模的结果。

第 $1,3,4$ 天的主菜分别是 $1,1,2$。第 $2$ 天不能选 $1$，否则前三天都相同，所以可以选 $2$ 或 $3$。第 $5$ 天可以选三种主菜中的任意一种，因此共有 $2\times3=6$ 种安排。 ## 样例 2 见 `考生目录/menu/menu2.in` 与 `考生目录/menu/menu2.ans`。该样例满足测试点 $1\sim6$ 的约束。 ## 样例 3 见 `考生目录/menu/menu3.in` 与 `考生目录/menu/menu3.ans`。该样例满足测试点 $7\sim20$ 的约束。 ## 样例 4 见 `考生目录/menu/menu4.in` 与 `考生目录/menu/menu4.ans`。该样例满足测试点 $7\sim20$ 的约束。 ## 样例 5 见 `考生目录/menu/menu5.in` 与 `考生目录/menu/menu5.ans`。该样例满足测试点 $7\sim20$ 的约束。 ## 样例 6 见 `考生目录/menu/menu6.in` 与 `考生目录/menu/menu6.ans`。该样例满足测试点 $7\sim20$ 的约束。 ## 数据范围 对于所有数据，保证 $1\le T\le10$。每组数据中，$3\le N\le100$，$1\le K\le N$，$1\le A_i\le N$，$1\le B_i\le3$，所有 $A_i$ 互不相同，且至少存在一种合法菜单安排。 | 测试点编号 | 附加限制（每组均满足） | | :--------: | :--------------------: | | $1\sim6$ | $N\le12$ | | $7\sim20$ | 无 |