配点: 100 点
問題
你喜欢面食,你每天都会做面食。你可以使用番茄酱、奶油酱或罗勒酱。 3 您可以制作不同类型的面食。
N 我决定考虑一下第二天的晚餐安排。在每一天 3 来自不同类型的面食 1 选择类型。但是,如果你连续吃同一种面食,你就会感到无聊,所以3 不要连续一天以上选择相同的面食。另外, 当日N 当日的 K 我已经决定了今天的面食。
作为输入 N 的值和K 给定每天的面食信息,计算有多少个时间表满足条件。 编写一个程序求除以 10\,000 后的余数。
入力
输入是 K + 1 行组成。
1 在线 2 整数 N, K (3 \leqq N \leqq 100,1 \leqq K \leqq N)以空格作为分隔符。
1 + i 行目 (1 \leqq i \leqq K) 是 写入 2 整数 A_i, B_i (1 \leqq A_i \leqq N,1 \leqq B_i \leqq 3)以空格作为分隔符。这是A_i 今天的面食已经决定了,B_i = 1 表示番茄酱,B_i = 2 表示奶油酱;B_i = 3 表示罗勒酱。A_i (1 \leqq i \leqq K)都是不同的。给定输入数据,满足条件的调度是 1 保证有多个。
出力
有多少计划符合条件? 输出为 10\,000 后的余数 1 请以行的形式输出。
入力例 1
5 3 3 1 1 1 4 2
出力例 1
6
入出力例 1 中,您 5 想想你的日常安排。1 日和 3 天是番茄酱,4 第一天是奶油酱。另外,3 不要连续一天以上选择同一种面食。该计划旨在满足这些条件。 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 。 你只需要砍掉