← 返回题目列表

AtCoder · joi2012yo_d

D. 面食

中文机器翻译题面 查看原题

配点: 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 。 你只需要砍掉