【集训队作业2018】strings
小p参加政治考试，总共有$n$道判断题。一些题目小p可以靠自己的能力蒙一个答案，然而对于一些他完全不会的题，他会通过某种方式得到标准答案然后填上去。小p具有时间倒流的能力，因此可以参加$q$次同样的考试，不过每次考试他的策略未必相同。众所周知，只有AK才能满足小p的欲望，而每道题的答案是未知的，小p想知道有多少种标准答案使得他在至少一次考试中能AK。
输入格式
第一行两个整数$n,q$。
下接$q$行，每行一个长为$n$的字符串，包含0 、1 、? 这三种字符，数字意味着答案是小p蒙的（可以匹配这种字符），$?$ 表示这道题他得到了标准答案（可以匹配任意字符）。
输出格式
一行一个整数，表示有多少长为$n$的$01$串$s$，使得$s$满足$q$ 个串中至少一个串的形式。
4 2
??01
1??1
6
共有这些合法的串：0001, 0101, 1001, 1101, 1011, 1111
限制与约定
| 子任务 | $n\leq$ | $q\leq$ | 特殊性质 | 分值 |
|---|---|---|---|---|
| 1 | $20$ | $20$ | $3$ | |
| 2 | $30$ | $20$ | $12$ | |
| 3 | $25$ | $30$ | $11$ | |
| 4 | $30$ | $30$ | $6$ | |
| 5 | $30$ | $100$ | 问号总数$\leq 40$ | $11$ |
| 6 | $30$ | $50$ | $16$ | |
| 7 | $30$ | $100$ | $41$ |
时间限制：$\texttt{1s}$
空间限制：$\texttt{512MB}$