Robot Tape Transformation

A robot is placed on a paper tape consisting of n cells (numbered 0 to n-1). Each cell initially contains either the digit 0, 1 or a blank represented by -. The robot’s tape is operated on by a predetermined operation‐sequence S which is a string over the alphabet {R, 0, 1, *}. There are m robots (each with its own tape) and each robot i is associated with an operation sequence Si.

Before executing the operations, the robot must choose a starting cell on its tape. All robots will use the same starting position p (with 0 ≤ p < n). After setting the starting position, the robot executes its operations one by one. The meanings of the operations are as follows:

• R: The robot moves one cell to the right. If there is no cell to the right (i.e. the robot would leave the tape), it explodes.
• 0: If the cell where the robot is standing is nonblank, it overwrites the cell with 0; otherwise nothing happens.
• 1: Similar to 0 but writes 1.
• *: If the cell is nonblank, the digit is flipped (i.e. 0 becomes 1 and vice‐versa); if the cell is blank, nothing happens.

For each tape the input is its initial configuration X (a string of length n over {0, 1, -}) and the output is the tape after the robot finishes its operations, denoted by Y. Notice that if a tape is completely blank initially then the robot does not perform any operation and the output remains all blanks. (In particular, note that a blank cell is never modified.)

For a fixed starting position p the robot will visit a sequence of cells. Its moves are determined solely by the occurrences of the command R in S (each R moves the robot one step to the right, and all other commands cause in‐place modifications). In other words, if we split S using R as the delimiter, we obtain r blocks (with r = (# of R’s) + 1). For the j‑th visited cell (that is, cell at index p + j, where 0 ≤ j < r) the modifications are determined by the j‑th block. In that block, if the cell’s initial value is a digit (0 or 1) it is transformed by a function f (which is computed by processing each character in the block in order) and the output is forced to be equal to f(x). If the cell is blank, it remains blank. For every cell that is not visited the output must equal the input.

Now, we are given for each robot its fixed operation sequence Si (which determines a factorization into blocks) and we want to count the number of ways to choose a pair of strings (Xi, Yi) (the input and target output for robot i) for each robot such that there exists at least one starting position p (with 0 ≤ p < n) satisfying all of the following for every robot:

• When starting at cell p, the robot never explodes (which imposes that p + Li < n, where Li is the maximum number of right‐moves required by the prefix of Si).
• The tape is modified exactly so that the output equals Yi (i.e. for visited cells the relation Y = f(X) holds according to the corresponding block, and on untouched cells Y = X).

Two overall configurations (the m pairs for the m robots) are considered different if there is at least one robot whose input or target output differs.

---

Counting Problem: Compute the number of ways to choose the m pairs of strings (Xi, Yi) (for 0 ≤ i < m) so that there exists at least one starting position p with the properties described above. Since the answer can be very large, output it modulo \(10^9+7\).

---

A word on the transformation functions: For each block (obtained by splitting S by R), a function \(f\) is computed on the digits \(0,1\). Initially \(f\) is the identity. Then for each character in the block:

• If the character is 0, then \(f(x)=0\) for any \(x\) (a constant function).
• If it is 1, then \(f(x)=1\) for all \(x\).
• If it is *, then \(f(x)\) is replaced by \(1-x\) (i.e. the negation of \(x\)) unless a constant writing has occurred; more precisely, applying * to the identity gives the negation and applying * to the negation returns the identity; similarly, applying * to a constant function swaps 0 and 1.

For a forced cell the rule is: if the cell’s initial symbol is a digit then the output is forced to \(f(x)\); if it is blank then it remains blank. (On non‐visited cells the tape remains unchanged, so Y = X.)

Remark: It turns out that for a fixed starting position the number of valid configurations for one robot is always \(3^n\) (because regardless of the restrictions the number factors multiply to \(3^n\)). However, as the starting position shifts the constraints occur on different sets of indices and many configurations are counted for more than one starting position. In our solution this overlap is taken into account. In fact, if for a given robot the block functions are all the identity, then the constraints from any starting position are identical and the total number of valid configurations for that robot is \(3^n\); otherwise the total number is

[ B = (n - r + 1);3^{n-r};F, \quad\text{where} \quad F = \prod_{k=0}^{r-1} (1+\varepsilon(f_k)), \quad \varepsilon(\mathrm{id})=2,; \varepsilon(\text{const})=1,; \varepsilon(\text{neg})=0, ]

and r = (# of R's in S) + 1 (the number of visited cells) (note that if (F=3^r) then all forced blocks are just the identity so the valid configurations do not depend on (p)). Finally, the answer is the product, over all robots, of the corresponding number (B_i); if for any robot no starting position is safe then the answer is 0.

inputFormat

The first line contains two integers m and n (1 ≤ m ≤ 1000, 1 ≤ n ≤ 32), denoting the number of robots and the length of the tape respectively.

Then follow m lines, each line containing a nonempty string Si consisting of characters from {R, 0, 1, *} – the operation sequence for robot i.

outputFormat

Output a single integer – the number of valid combinations of the m pairs (Xi, Yi) such that there exists at least one starting position p for which each robot does not explode and its tape is transformed as required. Since the number can be large, output it modulo \(10^9+7\).

sample

1 3
R

27

</p>