Monety: Fair Coin‐Stacks

Natalia and Cezary enjoy playing games – especially one they invented themselves. In this game a number of coin stacks are placed before them. Each stack consists of m coins arranged from top to bottom (as in a stack), and every coin is colored either blue or red.

The rules are as follows. When it is Natalia’s turn she may choose any blue coin in any stack and remove that coin along with all coins above it (i.e. the entire prefix in that stack). Similarly, when it is Cezary’s turn he may choose any red coin in any stack and remove that coin together with all coins above it. The players take turns; if on a player’s turn there is no legal move (i.e. in every stack, all coins that remain are of the opposite colour), then that player loses.

An initial configuration of stacks is called fair provided that, assuming both players play optimally, the second player wins – that is, the player who does not move first will always win. (Thus if, say, Natalia is the first to move then Cezary wins, and vice‐versa.)

Natalia and Cezary have already arranged the first k stacks (each containing exactly m coins). They now wish to complete the series – however, they agree that there is no sense in having more than n stacks in total. For every integer d in the interval [k, n], help them determine the number of different fair initial configurations consisting of d stacks (each stack with exactly m coins) that have the given k fixed stacks as their beginning. Two configurations are considered different if there exists some stack index i (1 ≤ i ≤ d) and coin position j (1 ≤ j ≤ m) such that the color of the j-th coin in the i-th stack is different between the two configurations.

Since the answer can be huge, output it modulo \(10^9+7\).

Note on the Game: This is a partisan game. Each stack (of m coins) is itself a game, defined recursively as follows. Let \(G(i)\) be the value of the stack when the coins from positions \(i\) to \(m\) remain (with \(G(m+1)=0\)). When it is Natalia’s turn in state \(i\) she may remove coins by choosing any index \(j\) (\(i\le j\le m\)) for which the \(j\)-th coin is blue, leaving the game in state \(j+1\). Similarly, when it is Cezary’s turn he may choose any index \(j\) (\(i\le j\le m\)) for which the coin is red. It turns out that every stack has a canonical value (a dyadic rational number, written in \(\LaTeX\) as, e.g., \(\frac{1}{2}\)). The overall game (the disjunctive sum of the stacks) is fair – i.e. a win for the second player – if and only if the sum of the values of the stacks is 0. In our problem, we define the value of a stack \(s\) as \(v(s)\) and we always work with its scaled version \(V(s)=v(s)\times2^m\) which is always an integer. (For example, when \(m=1\) a coin stack consisting of a blue coin has value 1 and so scaled value \(2\), and a red coin gives \(-2\). For \(m=2\) the four possible stacks have scaled values 8, -8, -2, and 2.)

Your task is to count, for every total number of stacks \(d\) with \(k\le d\le n\), the number of ways to choose the configuration of the remaining \(d-k\nobreak\) stacks (each of which may be any arrangement of m coins) so that the sum of the scaled values of all \(d\) stacks is 0. The arrangement of the first k stacks is given as input.

inputFormat

The input begins with three space‐separated integers k, n and m (0 ≤ k ≤ n, m ≥ 1). Here, k is the number of stacks already arranged, n is the maximum total number of stacks allowed, and m is the number of coins in each stack.

Then follow k lines. Each of these lines contains a string of length m consisting only of the characters B and R. The j-th character of a line denotes the color of the j-th coin (from top to bottom) in that stack. (If k is 0 then no such line appears.)

outputFormat

Output n-k+1 space‐separated integers. The i-th number (for 0 ≤ i ≤ n−k) should be the number of fair configurations (modulo \(10^9+7\)) when there are exactly k + i stacks in total.

sample

1 2 1
B

0 1