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

At any time, a robot must be standing on one of the cells of its paper tape. After setting the initial position of the robot on the tape, the $i$-th robot will sequentially execute a pre-defined operation sequence $S_i$, consisting of the characters 'R', '0', '1', and '*':

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 paper tape can be represented by a sequence of length $n$, where each element is 0, 1, or '-' (empty cell), representing the state of each cell in order. The initial state of the $i$-th paper 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 has no 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 paper tape where the $i$-th robot is located are empty, it will not perform any operations, and its output will be that all cells remain empty.

Now, Little R has provided 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 at the $p$-th cell of their respective tapes, execute all operations without exploding, and satisfy the condition that the output of the $i$-th robot 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. That is, how many ways are there to set the inputs $X_0, X_1, \dots, X_{m-1}$ and target outputs $Y_0, Y_1, \dots, Y_{m-1}$ for each robot such that there exists at least one position $p$ ($0 \le p < n$) where all robots can start at the $p$-th cell of their respective tapes, execute all operations without exploding, and satisfy the condition that the output of the $i$-th robot is $Y_i$. Please help Little D solve this problem. Since the final answer may be very large, please 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 between the two combinations.

Input

Read data from the file robot.in. The first line contains two positive integers $n, m$, representing the number of cells on each paper tape and the number of tapes, respectively. The next $m$ lines each contain a string $S_i$ consisting only of the characters 'R', '0', '1', and '*', representing the operation sequence for the $i$-th robot.

Output

Output to the file robot.out. A single line containing a single positive integer, representing the answer modulo $10^9 + 7$.

Examples

Input 1

2 1
1R*

Output 1

9

Input 2

3 2
1R0
*

Output 2

1468

Constraints

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: In each operation sequence, the number of 'R's is at most 15.