[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$ 取模后的余数。 两个组合方式不同当且仅当，存在至少一个机器人，它的输入或是目标输出在两个方式中不同。

第一行包含两个正整数 $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-` | `1-` | $0$ | | $4$ | `-0` | `-1` | $0$ | | $5$ | `-1` | `-0` | $0$ | | $6$ | `00` | `11` | $0$ | | $7$ | `10` | `11` | $0$ | | $8$ | `01` | `10` | $0$ | | $9$ | `11` | `10` | $0$ | 表中 `-` 表示空格子，注意方案 $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$ | $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$ 个。