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 自动生成