(note: actual in-contest limit was 3 seconds, a higher limit was picked here to allow more things to work)

There are ~m~ ~(1 \le m \le 1000)~ robots and ~m~ tapes. The ~i~-th robot ~(1 \le i \le m)~ works on tape ~i~. Each tape is divided into ~n~ ~(1 \le n \le 32)~ squares from left to right, and are numbered ~0, 1, \dots, n-1~. Each square has three possible states: (1) the square has number 0 (2) the square has number 1 (3) the square is empty.

At any point, a robot must stand in one of the squares of a tape. After setting the initial positions of the robots on the tapes, the ~i~-th robot will execute a predetermined sequence of operations ~S_i~. The operations consist of characters R, 0, 1, *.

• R means the robot will move one square right. If there are no squares to the right, the robot will explode.
• 0 means if the square the robot is currently at is nonempty, the robot will change the number in the square to 0. Otherwise, the robot will not modify the current square.
• 1 means if the square the robot is currently at is nonempty, the robot will change the number in the square to 1. Otherwise, the robot will not modify the current square.
• * means if the square the robot is currently at is nonempty, the robot will change the number ~x~ currently in the square into ~1-x~. Otherwise, the robot will not modify the current square.

The state of the ~i~-th tape may be represented by a string of length ~n~. Each character may be either 0, 1 or - (an empty square) representing the state of the corresponding square. The initial state of the ~i~-th tape is called the input to robot ~i~, ~X_i~. The state of the tape after the operations is called the output of robot ~i~, ~Y_i~. Notice if the robot explodes, the robot won't have any output.

It is easy to see if a square is empty, the robot will never modify the square, so robots have the following property: if on tape ~i~ (which is the tape robot ~i~ works on), all the squares are empty, then the robot will do nothing, and the output of the robot simply says all squares are empty.

Now given inputs ~X_i~ to the robots and initial target outputs ~Y_i~, we want to find a position ~p~ ~(0 \le p < n)~ such that all robots can use the ~p~-th square of the tape as the start position, finish all operations without exploding, and satisfy the condition that the ~i~-th robot has output ~Y_i~.

To make the problem harder, we want to know the number of combinations of inputs and outputs that have a feasible solution. In other words, we are interested in how many ways we may set the inputs to the robots ~X_0, X_1, \dots, X_{m-1}~ and the target outputs ~Y_0, Y_1, \dots, Y_{m-1}~ such that there exists at least one position ~p~ ~(0 \le p < n)~ such that all robots can set the ~p~-th square of the tape as the start position, finish all operations without exploding, and the output of the ~i~-th robot is ~Y_i~. Since the answer might be large, output the answer modulo ~10^9 + 7~. Two combinations are different if and only if there exists a robot such that its input or its output are different in the two combinations.

Input Specification

The first line contains two integers ~n,m~ denoting the number of squares on each tape and the number of tapes. In the following ~m~ lines, the ~i~-th line contains a string ~S_i~ consisting of characters R 0 1 *, denoting the sequence of operations of robot ~i~.

Output Specification

The output consists of only one integer denoting the answer modulo ~10^9 + 7~.

Sample Input 1

2 1
1R*

Sample Output 1

9

Explanation for Sample Output 1

The possible combinations are given below:

No.	~X_0~	~Y_0~	Feasible ~p~
1	--	--	~0,1~
2	0-	1-	~0~
3	1-	1-
4	-0	-1
5	-1	-0
6	00	11
7	10	11
8	01	10
9	11	10

Sample Input 2

3 2
1R0
*

Sample Output 2

1468

Explanation of Sample Output 2

We may compute the answer to this sample case using the inclusion-exclusion principle.

1. When ~p = 0~ is a feasible solution (i.e. after executing all the operations, all constraints are satisfied), then for square 0 of the first robot, either both the input and the output are empty, or the target output is 1. There are 3 possibilities. For square 1, either both the input and the output are empty, or the target output is 0, and there are 3 possibilities. Finally, for square 2, either both the input and the output are empty, or the input and the output are identical (since no operations are done for this square), and there are 3 possibilities. There are 27 possibilities for the first robot. For the second robot, for square 0 either both the input and the output are empty or the input and the target output are different. There are three possibilities. There are also 3 possibilities for square 1 and 2, so there are 27 possibilities for the second robot. In total, there shall be ~27 \times 27 = 729~ combinations.

2. When ~p = 1~ is a feasible solution, then for each of the three squares of the first tape (i.e. the tape of the first robot), there are three possibilities: for square 0 either the input and the output are empty or they are identical; for square 1 either both the input and the output are empty or the target output is 1; for square 2 either both the input and the output are empty or the output is 0. There are 27 possibilities for the first robot. For the second robot, for square 1 either both the input and the output are empty or they are different, so there are 3 possibilities. For square 0 and 2, either both the input and the output are empty, or the input and the output are identical, so there are 3 possibilities for each of the two squares. In total, there are ~27 \times 27 = 729~ combinations.

3. When ~p = 2~ is a feasible solution, then for the first robot, the inputs and the outputs are both empty (otherwise the first robot will explode). For the second robot, there are 27 possibilities.

4. If ~p = 0~ and ~p = 1~ are both feasible, then square 1 of the first robot must satisfy both the input and the output are empty. For square 0 of the first robot, either both the input and the output are empty or they are both 0. For square 2, either both the input and the output are empty or they are both 0. There are 4 possibilities for the first robot. For the second robot, square 0 and square 1 must be empty. There are 3 possibilities for square 2: either both the input and the output are empty or the input and the output are identical. There are 12 possibilities here.

5. If ~p = 0~ and ~p = 2~ are both feasible, then the inputs and the outputs of the first robot must be empty. Otherwise, the first robot will explode. For the second robot, square 0 and square 2 must be empty while there are 3 possibilities for square 1. There are 3 possibilities total.

6. If ~p = 1~ and ~p = 2~ are both feasible, then the inputs and the outputs of the first robot must be empty. For the second robot, square 1 and 2 must be empty, while there are 3 possibilities for square 0. There are 3 possibilities in total.

7. If ~p = 0,1,2~ are all feasible, then the inputs and the outputs of the two robots must be empty. There is only 1 possibility.

Therefore, by the inclusion-exclusion principle, the final answer is ~729+729+27-12-3-3+1 = 1468~.

Additional Samples

Additional samples can be found here.

Constraints

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

Test case	~n \le~	~m \le~	Additional Constraints
1~2	~1~	~1~	None.
3	~8~
4	~16~
5~6	~32~
7	~16~	~5~
8~10	~32~
11~12	~16~	~1000~
13~15	~32~		There are no R operations.
16~21			For each sequence of operations, there are at most 15 Rs.
22~25			None.