题目描述

小 R 有 $m$（$1 \le m \le 1000$）个机器人和 $m$ 张纸带，第 $i$（$1 \le i \le m$）个机器人负责对第 $i$ 张纸带进行操作。对于每张纸带，它们都被从左到右分成了 $n$（$1 \le n \le 32$）个格子，依次编号为 $0, 1, \ldots , n - 1$。每个格子有 $3$ 种状态：1. 格子上写有数字 $0$；2. 格子上写有数字 $1$；3. 格子是一个空格子。

在任意时刻，机器人必须站在纸带上的一个格子中。在设定好机器人在纸带上的初始位置后，第 $i$ 个机器人会依次执行预先设定的操作序列 $S_i$，操作由 R、0、1、* 四种字符组成，其中：

1. R 表示机器人向右走一格，如果右边没有格子，则机器人会原地爆炸；
2. 0 表示如果机器人所在格子非空，则将该格子上的数字改为 $0$，否则不修改；
3. 1 表示如果机器人所在格子非空，则将该格子上的数字改为 $1$，否则不修改；
4. * 表示如果机器人所在格子非空，则将格子上的数字 $x$ 改为 $1 - x$，否则不修改。

第 $i$ 张纸带的状态可以用一个长度为 $n$ 的序列表示，每个元素为 0、1 或 -（空格子），依次表示其每个格子的状态。第 $i$ 张纸带的初始状态称为机器人 $i$ 的输入 $X_i$，操作执行完成后纸带的状态称为机器人 $i$ 的输出 $Y_i$。注意，如果机器人爆炸了，那么这个机器人就没有输出。

可以发现，如果一个格子为空，那么机器人永远不会修改它。所以每个机器人都有如下特性：如果第 $i$ 个机器人所在的纸带上的所有格子都为空，那么它就不会执行任何操作，它的输出即为所有格子都为空。

现在小 R 给定了每一个机器人的输入 $X_i$（即每张纸带的初始状态）以及目标输出 $Y_i$。小 R 希望小 D 找到一个位置 $p$（$0 \le p < n$），使得所有机器人都能以其所在纸带的第 $p$ 个格子为初始位置，在不爆炸的情况下执行完所有操作，并且满足第 $i$ 个机器人的输出为 $Y_i$。

小 D 花了几毫秒解决了问题，现在他想知道，有多少个输入和输出的组合方式使得上述问题有解，即有多少种为每个机器人设定输入 $X_0, X_1, \ldots , X_{m - 1}$ 和目标输出 $Y_0, Y_1, \ldots , Y_{m - 1}$ 的方式，使得至少存在一个位置 $p$（$0 \le p < n$），使得所有机器人都能以其所在纸带的第 $p$ 个格子为起点，在不爆炸的情况下执行完所有操作，且满足第 $i$ 个机器人的输出为 $Y_i$。请你帮助小 D 解决这个问题，由于最终的答案可能很大，请你输出答案对 ${10}^9 + 7$ 取模后的余数。

两个组合方式不同当且仅当，存在至少一个机器人，它的输入或是目标输出在两个方式中不同。

输入格式

第一行包含两个正整数 $n, m$，分别表示每张纸带上的格子数和纸带数量。

接下来 $m$ 行，第 $i$ 行输入一个仅包含 R 0 1 * 这四种字符的字符串 $S_i$，表示第 $i$ 个机器人的操作序列。

输出格式

仅一行一个正整数，表示答案模 ${10}^9 + 7$ 后的余数。

2 1
1R*

9

3 2
1R0
*

1468

见附件中的 robot/robot3.in

见附件中的 robot/robot3.ans

见附件中的 robot/robot4.in

见附件中的 robot/robot4.ans

提示

【样例解释 #1】

方案编号	输入 $X_0$	目标输出 $Y_0$	可行初始位置 $p$
$1$	--		$0, 1$
$2$	0-	1-	$0$
$3$	1-
$4$	-0	-1
$5$	-1	-0
$6$	00	11
$7$	10
$8$	01	10
$9$	11

表中 - 表示空格子，注意方案 $1$ 中的输入和输出中有两个空格子。

当输入全为空时，初始位置可以是 $0$ 或 $1$，因为根据题意，输入全为空时机器人不会执行任何操作。

当输入不全为空时，初始位置只能为 $0$，如果初始位置为 $1$ 机器人一定会爆炸。所以此时实际执行的操作是将第一格的数字改为 $1$，并将第二格的数字 $x$ 改为 $1 - x$。

【样例解释 #2】

可以用容斥原理来计算这个样例。

1. 初始位置 $p = 0$ 可以使得执行完所有操作后满足条件。那么第一个机器人的纸带 $0$ 号格子要么输入输出都是空，要么目标输出是 $1$（输入无所谓），所以有 $3$ 种方案；$1$ 号格子要么输入输出都是空，要么目标输出是 $0$，也是 $3$ 种方案；$2$ 号格子要么输入输出都是空，要么输入和目标输出相同（因为没有对该格子执行任何操作），同样是 $3$ 种方案，共 $27$ 种方案。第二个机器人的 $0$ 号格子要么输入输出都是空，要么输入和目标输出不同，是 $3$ 种方案，$1$ 号和 $2$ 号格子也都是 $3$ 种方案，共 $27$ 种方案。所以总共 $27 \times 27 = 729$ 种方案。
2. 初始位置 $p = 1$ 可以使得执行完所有操作后满足条件。那么第一个机器人的纸带三个格子都是 $3$ 种方案，其中 $0$ 号格子要么输入输出都为空，要么相同；$1$ 号格子要么输入输出都为空，要么目标输出是 $1$；$2$ 号格子的输入输出要么都为空，要么输出是 $0$，共 $27$ 种方案。第二个机器人的 $1$ 号格子要么输入输出都是空，要么输入和目标输出不同，是 $3$ 种方案；$0$ 号和 $2$ 号格子要么输入输出都为空，要么输入输出相同，也都是 $3$ 种方案，共 $27$ 种方案。总共 $27 \times 27 = 729$ 种方案。
3. 初始位置 $p = 2$ 可以使得执行完所有操作后满足条件。那么第一个机器人的纸带必须输入输出全为空（否则爆炸），只有 $1$ 种方案。第二个机器人是 $27$ 种方案，总共 $27$ 种方案。
4. 初始位置 $p = 0, 1$ 都满足条件。这要求第一个机器人的 $1$ 号格子输入输出都为空；$0$ 号格子的输入输出都为空或都为 $1$；$2$ 号格子的输入输出都为空或都为 $0$，所以第一个机器人的纸带有 $4$ 种方案。第二个机器人 $0$ 号格子和 $1$ 号格子都为空，$2$ 号格子有 $3$ 种方案，第二个机器人的 $0$ 号和 $1$ 号格子必须都为空，$2$ 号格子要么输入输出都为空，要么输入和输出相同，有 $3$ 种方案。总共 $12$ 种方案。
5. 初始位置 $p = 0, 2$ 都满足条件。那么第一个机器人的纸带必须输入输出全为空（否则爆炸），只有 $1$ 种方案。第二个机器人 $0$ 号和 $2$ 号格子都为空，$1$ 号格子有 $3$ 种方案。总共 $3$ 种方案。
6. 初始位置 $p = 1, 2$ 都满足条件。那么第一个机器人的纸带必须输入输出全为空，只有 $1$ 种方案。第二个机器人 $1$ 号和 $2$ 号格子都为空，$0$ 号格子有 $3$ 种方案。总共 $3$ 种方案。
7. 初始位置 $p = 0, 1, 2$ 都满足条件。那么两个机器人的输入输出必须都为空，总共 $1$ 种方案。

根据容斥原理，最后的答案为 $729 + 729 + 27 - 12 - 3 - 3 + 1 = 1468$。

【数据范围】

对于所有测试点：$1 \le n \le 32$，$1 \le m \le 1000$，$1 \le \lvert S_i \rvert \le 100$。

测试点编号	$n \le$	$m \le$	特殊限制
$1 \sim 2$	$1$	$1$	无
$3$	$8$
$4$	$16$
$5 \sim 6$	$32$
$7$	$16$	$5$
$8 \sim 10$	$32$
$11 \sim 12$	$16$	$1000$
$13 \sim 15$	$32$		A
$16 \sim 21$			B
$22 \sim 25$			无

特殊限制 A：操作序列中不存在 R。

特殊限制 B：每个操作序列中，R 的数量至多 $15$ 个。