问题描述

具体描述见教材p173： 假设字符串由字符 "0","1","" 组成，其中字符 "" 表示该字符可由字符 "0" 或 "1" ，替代。 现有一些字符串，根据这些字符串生成所有可生成的字符串。如： {10,1,0} 可生成 {10,01,11,00} {101,001,*01} 可生成 {101, 001} 注意：后一个例子中 "*01" 并没有生成新的字符串。

格式

输入

第１行是两个整数ｍ，ｎ（1<=m<=15, 1<=n<=2500)。m表示字符串的长度，ｎ表示字符串的个数。 以下ｎ行每行各有一个字符串。文件中各行的行首、行末没有多余的空格。

输出

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

样例

2 3
10
*1
0*

4

限制

1s, 64MB.