Natalia and Cezary like to play games, especially those they invent themselves. They decided to arrange a sequence of coin stacks, each containing $m$ coins, where each coin is either blue or red. In her turn, Natalia can choose any blue coin and remove it from the game along with all coins above it in the stack. Similarly, in his turn, Cezary can choose any red coin and remove it and all coins above it in the same stack. Players take turns, and the player who cannot make a valid move loses—that is, when all their coins have already been removed from the game.

Knowing the rules, they must now determine the initial state of the game: a sequence of $d$ stacks, each containing exactly $m$ coins. Neither Natalia nor Cezary wants an unfair advantage, so they agreed that the sequence of stacks must be fair. A sequence of stacks is called fair if, assuming Natalia and Cezary play optimally, the player who does not make the first move wins the game. Thus, if Natalia makes the first move, Cezary wins with optimal strategy, and vice versa: if Cezary starts, Natalia wins.

The pair has already arranged the first $k$ stacks of $m$ coins each. Now they are wondering how to complete this sequence of stacks. They have already concluded that it makes no sense to have more than $n$ stacks in the game. Help them, and for each number $d$ in the range $[k, n]$, determine how many different fair sequences of $d$ stacks of $m$ coins exist that begin with the sequence of stacks they have already arranged. Two sequences of stacks are considered different if there exist $i \in [1, d]$ and $j \in [1, m]$ such that the $j$-th coin in the $i$-th stack is blue in one sequence and red in the other.

Since these results can be very large, it is sufficient to provide their remainders modulo $10^9 + 7$.

Input

The first line of standard input contains three integers $n, m$, and $k$ ($1 \le n \le 32$; $1 \le m \le 24$; $0 \le k \le n$), representing the limit on the number of stacks, the number of coins in each stack, and the number of already created stacks, respectively.

The next $k$ lines contain descriptions of the already placed stacks; the $i$-th line contains a string of characters 'N' and 'C' of length exactly $m$, which denotes the colors of the coins in the $i$-th stack, starting from the bottom. If the $j$-th character of this string is 'N', then the $j$-th coin from the bottom in the $i$-th stack is blue. Otherwise, the character is 'C', and that coin is red.

Output

The single line of output should contain a sequence of $n - k + 1$ integers, where the $i$-th integer should be the remainder modulo $10^9 + 7$ of the number of ways to extend the sequence by $i - 1$ stacks such that the final sequence of stacks is fair.

Examples

Input 1

3 3 1
CCN

Output 1

0 1 3

Input 2

2 1 0

Output 2

1 0 2

Input 3

4 2 4
CN
NC
CC
NN

Output 3

1

Note

In the first example, if we do not add any stacks, the single-element sequence will not be fair. However, we can add the stack NNC – such a sequence of two stacks will be fair. We can add two stacks in three ways: [CCN, NNN], [NNN, CCN], [NCN, NCN].

Subtasks

• In some test groups, the condition $k = n$ holds.
• In some test groups, the conditions $n \le 8$ and $m \le 8$ hold.
• In some test groups, the conditions $n \le 12$ and $m \le 13$ hold.
• In some test groups, the condition $n \le 16$ and $m \le 19$ holds.

Each case mentioned above describes at least one group not mentioned in previous cases.