AT_joi2012yo_d パスタ (Pasta)

你特别喜欢意大利面，每天晚餐都会做来吃。你能够制作三种意大利面：番茄酱、奶油酱和罗勒酱。 现在你打算为未来 $N$ 天的晚餐做出计划。对于每一天，你需要从这三种意大利面中选择一种。为了不失去新鲜感，你不能连续三天选择同一种意大利面。此外，你已经为其中的 $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$，表示第 $A_i$ 天的晚餐已经确定为第 $B_i$ 种意大利面（$1 \leq A_i \leq N$，$1 \leq B_i \leq 3$）。每个 $A_i$ 是唯一的。保证至少有一种满足条件的方案。

输出符合条件的晚餐计划方案数对 $10\,000$ 取模的结果。 ## 数据范围与说明 ### 示例解释 1 在示例 1 中，你需要规划 $5$ 天的晚餐。第 $1$ 天和第 $3$ 天已确定为番茄酱，第 $4$ 天为奶油酱。同时，要满足连续三天不能选择同一种意大利面的条件。总共有 $6$ 种符合条件的方案。 在表格中，$1$ 表示番茄酱，$2$ 表示奶油酱，$3$ 表示罗勒酱。 ### 示例解释 2 在示例 2 中，满足条件的方案有 $4\,112\,640$ 种。将这个数对 $10\,000$ 取余，结果是 $2\,640$。 **本翻译由 AI 自动生成**

### Sample Explanation 1 入出力例 $ 1 $ において，あなたは $ 5 $ 日間の予定を考える．$ 1 $ 日目と $ 3 $ 日目はトマトソースであり，$ 4 $ 日目はクリームソースである．また，$ 3 $ 日以上連続して同じパスタを選んではいけない．これらの条件をみたす予定は $ 6 $ 通りある． !\[2012-yo-t4-fig01.png\](https://img.atcoder.jp/joi2012yo/2012-yo-t4-fig01.png) この表では，$ 1 $ はトマトソースを，$ 2 $ はクリームソースを，$ 3 $ はバジルソースを表す． - - - - - - ### Sample Explanation 2 入出力例 $ 2 $ において，条件をみたす予定は全部で $ 4\,112\,640 $ 通りある．それを $ 10\,000 $ で割った余りである $ 2\,640 $ を出力する．