题目描述

假设字符串只由字符‘0’，‘1’，‘*’组成，其中字符‘*’表示该字符可由字符‘0’或‘1’替代。 现有一些字符串，根据这些字符串生成所有可生成的字符串。如： {10，*1，*0}可生成{10，01，11，00 } {101，001，*01}可生成{ 101，001} 注意后一个例子中‘*01’并没有生成新的字符串。

输入格式

第一行是两个整数m，n。（1≤m≤15,1≤n≤2500）m表示字符串的长度，n表示字符串的个数。两个整数之间由一个空格隔开。以下n行每行各有一个字符串。文件中各行的行首、行末没有多余的空格。

输出格式

输出文件只有一个整数，表示所能生成的字符串的个数。

2 3
10
*1
0*

4

提示

本题共 10 个测试点。

来源