P7740 [NOI2021] Robot Game

Little R has $m$ ($1 \le m \le 1000$) robots and $m$ paper tapes. The $i$-th ($1 \le i \le m$) robot is responsible for operating on the $i$-th tape. Each tape is divided from left to right into $n$ ($1 \le n \le 32$) cells, numbered $0, 1, \ldots, n - 1$ in order. Each cell has $3$ possible states: 1. the cell contains digit $0$; 2. the cell contains digit $1$; 3. the cell is empty. At any moment, a robot **must** stand on a cell on its tape. After setting the robot’s initial position on the tape, the $i$-th robot will execute a pre-defined operation sequence $S_i$ in order. The operations are given by four characters: `R`, `0`, `1`, `*`, where: 1. `R` means the robot moves one cell to the right. If there is no cell to the right, the robot explodes on the spot. 2. `0` means: if the cell the robot is currently on is not empty, change the digit in that cell to $0$; otherwise, do nothing. 3. `1` means: if the cell the robot is currently on is not empty, change the digit in that cell to $1$; otherwise, do nothing. 4. `*` means: if the cell the robot is currently on is not empty, change the digit $x$ in that cell to $1 - x$; otherwise, do nothing. The state of the $i$-th tape can be represented as a sequence of length $n$, where each element is `0`, `1`, or `-` (empty), describing the state of each cell in order. The initial state of the $i$-th tape is called robot $i$’s input $X_i$, and the tape state after all operations are executed is called robot $i$’s output $Y_i$. Note that if a robot explodes, then it has no output. You can see that if a cell is empty, the robot will never modify it. Therefore, each robot has the following property: if **all cells** on the tape of the $i$-th robot are empty, then it will not execute any operations, and its output is that all cells are empty. Now Little R provides each robot’s input $X_i$ (i.e. the initial state of each tape) and the target output $Y_i$. Little R wants Little D to find a position $p$ ($0 \le p < n$) such that **all robots** can start at cell $p$ on their own tapes, finish all operations without exploding, and satisfy that the output of robot $i$ is $Y_i$. Little D solved the problem in a few milliseconds. Now he wants to know: how many combinations of inputs and outputs make the above problem solvable? In other words, how many ways are there to set inputs $X_0, X_1, \ldots, X_{m - 1}$ and target outputs $Y_0, Y_1, \ldots, Y_{m - 1}$ for all robots such that there exists at least one position $p$ ($0 \le p < n$) where all robots can start from cell $p$ on their own tapes, finish all operations without exploding, and satisfy that the output of robot $i$ is $Y_i$? Please help Little D solve this problem. Since the final answer may be very large, output the result modulo ${10}^9 + 7$. Two combinations are different if and only if there exists at least one robot whose input or target output differs between the two combinations.

The first line contains two positive integers $n, m$, representing the number of cells on each tape and the number of tapes. The next $m$ lines each contain a string $S_i$ consisting only of the four characters `R` `0` `1` `*`, representing the operation sequence of the $i$-th robot.

Output a single positive integer: the answer modulo ${10}^9 + 7$.

**[Sample Explanation #1]** | Plan ID | Input $X_0$ | Target output $Y_0$ | Feasible starting positions $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$ | In the table, `-` means an empty cell. Note that in plan $1$, there are two empty cells in both the input and the output. When the input is all empty, the starting position can be $0$ or $1$, because by the statement, when the input is all empty, the robot will not execute any operations. When the input is not all empty, the starting position can only be $0$. If the starting position is $1$, the robot will definitely explode. So in this case, the actual executed operations are: change the digit in the first cell to $1$, and change the digit $x$ in the second cell to $1 - x$. **[Sample Explanation #2]** This sample can be computed using the inclusion-exclusion principle. 1. Starting position $p = 0$ can make the condition hold after all operations are executed. Then for the first robot, cell $0$ is either empty in both input and output, or the target output is $1$ (the input does not matter), so there are $3$ possibilities. For cell $1$, it is either empty in both input and output, or the target output is $0$, also $3$ possibilities. For cell $2$, it is either empty in both input and output, or the input equals the target output (because no operation is performed on this cell), also $3$ possibilities. So there are $27$ possibilities in total. For the second robot, cell $0$ is either empty in both input and output, or the input differs from the target output, giving $3$ possibilities; cells $1$ and $2$ also each have $3$ possibilities, so there are $27$ possibilities in total. Therefore, there are $27 \times 27 = 729$ possibilities in total. 2. Starting position $p = 1$ can make the condition hold after all operations are executed. Then each of the three cells on the first robot’s tape has $3$ possibilities: for cell $0$, it is either empty in both input and output, or they are equal; for cell $1$, it is either empty in both input and output, or the target output is $1$; for cell $2$, it is either empty in both input and output, or the output is $0$. So there are $27$ possibilities. For the second robot, cell $1$ is either empty in both input and output, or the input differs from the target output, giving $3$ possibilities; for cells $0$ and $2$, they are either empty in both input and output, or the input equals the output, also $3$ possibilities each, for a total of $27$ possibilities. Therefore, there are $27 \times 27 = 729$ possibilities in total. 3. Starting position $p = 2$ can make the condition hold after all operations are executed. Then the first robot’s tape must be all empty in both input and output (otherwise it explodes), so there is only $1$ possibility. The second robot has $27$ possibilities, so there are $27$ possibilities in total. 4. Both starting positions $p = 0, 1$ satisfy the condition. This requires that for the first robot, cell $1$ is empty in both input and output; for cell $0$, input and output are either both empty or both $1$; for cell $2$, input and output are either both empty or both $0$. So the first robot’s tape has $4$ possibilities. For the second robot, cells $0$ and $1$ are empty, and cell $2$ has $3$ possibilities; equivalently, cells $0$ and $1$ must both be empty, and cell $2$ is either empty in both input and output, or input equals output, giving $3$ possibilities. There are $12$ possibilities in total. 5. Both starting positions $p = 0, 2$ satisfy the condition. Then the first robot’s tape must be all empty in both input and output (otherwise it explodes), so there is only $1$ possibility. For the second robot, cells $0$ and $2$ are empty, and cell $1$ has $3$ possibilities. There are $3$ possibilities in total. 6. Both starting positions $p = 1, 2$ satisfy the condition. Then the first robot’s tape must be all empty in both input and output, so there is only $1$ possibility. For the second robot, cells $1$ and $2$ are empty, and cell $0$ has $3$ possibilities. There are $3$ possibilities in total. 7. Starting positions $p = 0, 1, 2$ all satisfy the condition. Then the inputs and outputs of both robots must be all empty. There is $1$ possibility in total. By inclusion-exclusion, the final answer is $729 + 729 + 27 - 12 - 3 - 3 + 1 = 1468$. **[Constraints]** For all test points: $1 \le n \le 32$, $1 \le m \le 1000$, $1 \le \lvert S_i \rvert \le 100$. | Test point ID | $n \le$ | $m \le$ | Special constraints | |:-:|:-:|:-:|:-:| | $1 \sim 2$ | $1$ | $1$ | None | | $3$ | $8$ | $1$ | None | | $4$ | $16$ | $1$ | None | | $5 \sim 6$ | $32$ | $1$ | None | | $7$ | $16$ | $5$ | None | | $8 \sim 10$ | $32$ | $5$ | None | | $11 \sim 12$ | $16$ | $1000$ | None | | $13 \sim 15$ | $32$ | $1000$ | A | | $16 \sim 21$ | $32$ | $1000$ | B | | $22 \sim 25$ | $32$ | $1000$ | None | Special constraint A: there is no `R` in the operation sequence. Special constraint B: in each operation sequence, the number of `R` is at most $15$. Translated by ChatGPT 5