Coins

Natalia and Cezary like games, especially ones they invented themselves. They decided to lay out a row of coin stacks, with exactly $m$ coins in each stack, where every coin is either blue or red. On her turn, Natalia picks any blue coin and removes it from the game together with all coins above it in its stack. On his turn, Cezary picks any red coin and removes it together with all coins above it in the same stack. The players move in turns, and whoever cannot make a legal move loses. That happens when all of their coins have already been removed.

A row of stacks is called fair if, when both players play optimally, the player who does not make the first move wins. In other words, if Natalia moves first, Cezary wins under optimal play, and if Cezary moves first, Natalia wins.

The pair has already built the first $k$ stacks, with $m$ coins each. They are now deciding how to finish the row. They concluded that the game should have no more than $n$ stacks. For each $d \in [k, n]$, count the fair rows of $d$ stacks with $m$ coins each that begin with the stacks they have already built. Two rows are different if there exist $i \in [1, d]$ and $j \in [1, m]$ such that the $j$-th coin of the $i$-th stack is blue in one row and red in the other.

Since the answers can be very large, print them modulo $10^9 + 7$.

The first line contains three integers $n$, $m$, and $k$: the limit on the number of stacks, the number of coins in each stack, and the number of stacks already built. Constraints: $1 \le n \le 32$, $1 \le m \le 24$, $0 \le k \le n$. The next $k$ lines describe the existing stacks. Line $i$ is a string of exactly $m$ characters 'N' and 'C' that lists the colors of the $i$-th stack from the bottom. If the $j$-th character is 'N', the $j$-th coin from the bottom is blue. Otherwise the character is 'C' and that coin is red.

Print one line with $n - k + 1$ integers separated by spaces. The $i$-th integer is the number of ways to add $i - 1$ stacks so that the final row is fair, modulo $10^9 + 7$.

Explanation of the first example: if no stacks are added, a row with a single stack is not fair. Adding one NNC stack makes a two-stack row fair. There are three ways to add two stacks: [CCN, NNN], [NNN, CCN], and [NCN, NCN].