A6577. 「NOI2021」机器人游戏

小 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$ 取模后的余数。

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

从文件 robot.in 读入数据。

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

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

输出到文件 robot.out 中。

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

对于所有测试点：$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$ | $1$ | 无 |
| $4$ | $16$ | $1$ | 无 |
| $5 \sim 6$ | $32$ | $1$ | 无 |
| $7$ | $16$ | $5$ | 无 |
| $8 \sim 10$ | $32$ | $5$ | 无 |
| $11 \sim 12$ | $16$ | $1000$ | 无 |
| $13 \sim 15$ | $32$ | $1000$ | A |
| $16 \sim 21$ | $32$ | $1000$ | B |
| $22 \sim 25$ | $32$ | $1000$ | 无 |

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

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