题目描述

小 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$ 种状态：

• 格子上写有数字 $0$；

• 格子上写有数字 $1$；

• 格子是一个空格子。

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

• R 表示机器人向右走一格，如果右边没有格子，则机器人会原地爆炸；

• 0 表示如果机器人所在格子非空，则将该格子上的数字改为 $0$，否则不修改；

• 1 表示如果机器人所在格子非空，则将该格子上的数字改为 $1$，否则不修改；

• *表示如果机器人所在格子非空，则将格子上的数字 $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$ 取模后的余数。

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

输入格式

从文件 robot.in 读入数据。

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

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

输出格式

输出到文件 robot.out 中。

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

2 1
1R*

9

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

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

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

数据规模与约定

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