← 返回题目列表

Codeforces · 47/D

D. 安全

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

Vasya 试图闯入保险箱。他知道密码由 n 个数字组成,每个数字都是 0 或 1。 Vasya 已尝试输入该密码 m 次。每次尝试后,系统都会告诉他正确的数字在多少个位置。没有说明错误的数字位于哪个位置。 Vasya 太不幸了,他没有输入超过 5 个正确数字的代码。现在瓦夏完全困惑了:他认为系统有错误,而且是自相矛盾的。帮助 Vasya — 计算剩下多少种可能的代码变体,这些变体与之前的系统响应不矛盾。

输入

第一输入行包含两个整数 n 和 m (6 ≤ n ≤ 35, 1 ≤ m ≤ 10),它们代表代码中的数字数量和 Vasya 的尝试次数。然后是 m 行,每行包含空格分隔的 si 和 ci,它们相应地表示 Vasya 的尝试(包含 n 个数字(0 或 1))和系统的响应(0 到 5 之间的整数)。

输出

打印单个数字,该数字指示还剩下多少种与 m 系统响应不矛盾的可能代码变体。

示例

输入 #1

6 2
000000 2
010100 4

输出 #1

6

输入 #2

6 3
000000 2
010100 4
111100 0

输出 #2

0

输入 #3

6 3
000000 2
010100 4
111100 2

输出 #3

1