题目描述

假设字符串只由字符 “0”，“1”，“*” 组成，其中字符 “*” 表示该字符可由字符 “0” 或 “1” 替代。

现有一些字符串，根据这些字符串生成所有可生成的字符串。如：

{10，*1，0*} 可生成 {10，01，11，00}；

{101，001，*01} 可生成 {101，001}；

注意后一个例子中“*01”并没有生成新的字符串。

输入格式

第一行是两个整数 $m$，$n$（$1 \le m ≤ 15$，$1 \le n \le 2500$）。$m$ 表示字符串的长度，$n$ 表示字符串的个数。

以下 $n$ 行每行各有一个字符串。文件中各行的行首、行末没有多余的空格。

输出格式

一个整数，表示所能生成的字符串的个数。

样例

2 3
10
*1
0*

4