题目描述

假设一个字符串只由字符 ‘0’，‘1’，‘*’ 组成，其中字符 ‘*’ 表示该字符可由字符 ‘0’ 或 ‘1’ 替代。

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

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

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

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

输入格式

第一行是两个整数 M , N ( 1 ≤ M ≤ 15 , 0 ≤ N ≤ 2500 )。M 表示字符串的长度，N 表示字符串的个数。两个整数之间由一个空格隔开。

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

输出格式

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

样例

2 3
10
*1
0*

4