Problem Description

Little R has $m$ ($1 \le m \le 1000$) robots and $m$ tapes. The $i$-th ($1 \le i \le m$) robot is responsible for operating on the $i$-th tape. Each tape is divided into $n$ ($1 \le n \le 32$) cells from left to right, numbered as $0, 1, \ldots, n - 1$. Each cell can be in one of three states: 1. the cell contains the digit $0$; 2. the cell contains the digit $1$; 3. the cell is empty.

At any time, a robot must be positioned on a cell of the tape. After setting the initial position of the robot on the tape, the $i$-th robot will execute a predefined sequence of operations $S_i$, which consists of the characters R, 0, 1, and *. The meanings of these characters are as follows:

1. R means the robot moves one cell to the right. If there are no more cells to the right, the robot will explode.
2. 0 means if the cell the robot is on is not empty, it changes the digit in that cell to $0$, otherwise it does not modify the cell.
3. 1 means if the cell the robot is on is not empty, it changes the digit in that cell to $1$, otherwise it does not modify the cell.
4. * means if the cell the robot is on is not empty, it changes the digit $x$ in that cell to $1 - x$, otherwise it does not modify the cell.

The state of the $i$-th tape can be represented by a sequence of length $n$, where each element is 0, 1, or - (empty cell), indicating the state of each cell. The initial state of the $i$-th tape is called the input $X_i$ for robot $i$, and the state of the tape after the operations are completed is called the output $Y_i$ for robot $i$. Note that if a robot explodes, it does not produce an output.

It can be observed 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, it will not perform any operations, and its output will be all empty cells.

Now, Little R has specified the input $X_i$ (the initial state of each tape) and the target output $Y_i$ for each robot. Little R wants Little D to find a position $p$ ($0 \le p < n$) such that all robots can start from the $p$-th cell of their respective tapes, execute their operations without exploding, and achieve the target output $Y_i$.

Little D spent a few milliseconds solving the problem. Now he wants to know how many combinations of inputs and outputs exist such that the problem is solvable, i.e., how many ways there are to set the inputs $X_0, X_1, \ldots, X_{m - 1}$ and the target outputs $Y_0, Y_1, \ldots, Y_{m - 1}$ for each robot, such that there exists at least one position $p$ ($0 \le p < n$) where all robots can start from the $p$-th cell of their respective tapes, execute their operations without exploding, and achieve the target output $Y_i$. Please help Little D solve this problem. Since the final answer may be very large, output the answer modulo ${10}^9 + 7$.

Two combinations are considered different if and only if there exists at least one robot whose input or target output is different in the two combinations.

Input Format

The first line contains two positive integers $n$ and $m$, representing the number of cells on each tape and the number of tapes, respectively.

The next $m$ lines, the $i$-th line contains a string $S_i$ consisting only of the characters R, 0, 1, and *, representing the sequence of operations for the $i$-th robot.

Output Format

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

Sample Input and Output

Input Sample #1

2 1
1R*

Output Sample #1

9

Input Sample #2

3 2
1R0
*

Output Sample #2

1468

Input Sample #3

See attached file robot/robot3.in

Output Sample #3

See attached file robot/robot3.ans

Input Sample #4

See attached file robot/robot4.in

Output Sample #4

See attached file robot/robot4.ans

Notes/Hints

[Sample Explanation #1]

In the table, - represents an empty cell. Note that in scheme $1$, both the input and output have two empty cells.

When the input is all empty, the initial position can be either $0$ or $1$, as per the problem statement, the robot will not perform any operations if the input is all empty.

When the input is not all empty, the initial position can only be $0$. If the initial position is $1$, the robot will definitely explode. Therefore, the actual operation in this case is to 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 example can be calculated using the principle of inclusion-exclusion.

1. The initial position $p = 0$ can satisfy the condition after all operations are completed. Then, for the first robot, the $0$-th cell either has empty input and output or the target output is $1$ (the input does not matter), so there are $3$ schemes; the $1$-th cell either has empty input and output or the target output is $0$, also $3$ schemes; the $2$-th cell either has empty input and output or the input and target output are the same (since no operation is performed on this cell), also $3$ schemes, totaling $27$ schemes. For the second robot, the $0$-th cell either has empty input and output or the input and target output are different, $3$ schemes, the $1$-th and $2$-th cells are also $3$ schemes each, totaling $27$ schemes. So in total, $27 \times 27 = 729$ schemes.
2. The initial position $p = 1$ can satisfy the condition after all operations are completed. Then, for the first robot, all three cells of the tape are $3$ schemes each, where the $0$-th cell either has empty input and output or they are the same; the $1$-th cell either has empty input and output or the target output is $1$; the $2$-th cell's input and output either are both empty or the output is $0$, totaling $27$ schemes. For the second robot, the $1$-th cell either has empty input and output or the input and target output are different, $3$ schemes; the $0$-th and $2$-th cells either have empty input and output or the input and output are the same, also $3$ schemes each, totaling $27$ schemes. In total, $27 \times 27 = 729$ schemes.
3. The initial position $p = 2$ can satisfy the condition after all operations are completed. Then, for the first robot, the tape must have all empty input and output (otherwise it will explode), only $1$ scheme. For the second robot, $27$ schemes, totaling $27$ schemes.
4. The initial positions $p = 0, 1$ both satisfy the condition. This requires the first robot's $1$-th cell to have empty input and output; the $0$-th cell's input and output to be both empty or both $1$; the $2$-th cell's input and output to be both empty or both $0$, so the first robot's tape has $4$ schemes. For the second robot, the $0$-th and $1$-th cells must be empty, the $2$-th cell either has empty input and output or the input and output are the same, $3$ schemes. In total, $12$ schemes.
5. The initial positions $p = 0, 2$ both satisfy the condition. Then, for the first robot, the tape must have all empty input and output (otherwise it will explode), only $1$ scheme. For the second robot, the $0$-th and $2$-th cells must be empty, the $1$-th cell has $3$ schemes. In total, $3$ schemes.
6. The initial positions $p = 1, 2$ both satisfy the condition. Then, for the first robot, the tape must have all empty input and output, only $1$ scheme. For the second robot, the $1$-th and $2$-th cells must be empty, the $0$-th cell has $3$ schemes. In total, $3$ schemes.
7. The initial positions $p = 0, 1, 2$ all satisfy the condition. Then, both robots' input and output must be all empty, totaling $1$ scheme.

According to the principle of inclusion-exclusion, the final answer is $729 + 729 + 27 - 12 - 3 - 3 + 1 = 1468$.

[Data Range]

For all test cases: $1 \le n \le 32$, $1 \le m \le 1000$, $1 \le |S_i| \le 100$.

Special Constraint A: The operation sequence does not contain R.

Special Constraint B: Each operation sequence contains at most $15$ Rs.

见题面 Input 部分

见题面 Output 部分