UOJ Logo Universal Online Judge

UOJ

#425. 【集训队作业2018】strings

统计

小p参加政治考试,总共有$n$道判断题。一些题目小p可以靠自己的能力蒙一个答案,然而对于一些他完全不会的题,他会通过某种方式得到标准答案然后填上去。小p具有时间倒流的能力,因此可以参加$q$次同样的考试,不过每次考试他的策略未必相同。众所周知,只有AK才能满足小p的欲望,而每道题的答案是未知的,小p想知道有多少种标准答案使得他在至少一次考试中能AK。

输入格式

第一行两个整数$n,q$。

下接$q$行,每行一个长为$n$的字符串,包含01? 这三种字符,数字意味着答案是小p蒙的(可以匹配这种字符),$?$ 表示这道题他得到了标准答案(可以匹配任意字符)。

输出格式

一行一个整数,表示有多少长为$n$的$01$串$s$,使得$s$满足$q$ 个串中至少一个串的形式。

样例一

input

4 2
??01
1??1

output

6

explanation

共有这些合法的串: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}$

下载

样例数据下载