CF47D.Safe

Vasya tries to break in a safe. He knows that a code consists of n numbers, and every number is a 0 or a 1. Vasya has made m attempts to enter the code. After each attempt the system told him in how many position stand the right numbers. It is not said in which positions the wrong numbers stand. Vasya has been so unlucky that he hasn’t entered the code where would be more than 5 correct numbers. Now Vasya is completely bewildered: he thinks there’s a mistake in the system and it is self-contradictory. Help Vasya — calculate how many possible code variants are left that do not contradict the previous system responses.

瓦西娅试图破解一个保险箱。他知道密码由 $n$ 个数字组成，每个数字为 $0$ 或 $1$。瓦西娅已进行了 $m$ 次密码输入尝试。每次尝试后，系统会告诉他有多少个位置上的数字是正确的（即与真实密码在该位置上的数字相同），但并未指出具体哪些位置正确。瓦西娅非常不走运，以至于他所有尝试中，正确数字的个数均未超过 $5$ 个。现在瓦西娅完全困惑了：他认为系统存在错误，其反馈自相矛盾。请帮助瓦西娅——计算出所有与之前系统反馈均不矛盾的可能密码数量。

The first input line contains two integers n and m (6 ≤ n ≤ 35, 1 ≤ m ≤ 10) which represent the number of numbers in the code and the number of attempts made by Vasya. Then follow m lines, each containing space-separated s__i and c__i which correspondingly indicate Vasya’s attempt (a line containing n numbers which are 0 or 1) and the system’s response (an integer from 0 to 5 inclusively).

第一行输入包含两个整数 $n$ 和 $m$（$6 \leq n \leq 35$，$1 \leq m \leq 10$），分别表示密码中数字的个数以及 Vasya 所做的尝试次数。接下来是 $m$ 行，每行包含用空格分隔的 $s_i$ 和 $c_i$，分别对应 Vasya 的一次尝试（一行包含 $n$ 个数字，每个数字为 $0$ 或 $1$）以及系统给出的反馈（一个介于 $0$ 到 $5$（含）之间的整数）。

Print the single number which indicates how many possible code variants that do not contradict the m system responses are left.

输出一个单独的数字，表示剩余多少种可能的密码组合不与这 m 条系统反馈相矛盾。