Natalia et Cezary aiment jouer à des jeux, et surtout à ceux qu'ils inventent eux-mêmes. Ils ont décidé de disposer devant eux une suite de piles de pièces, chacune contenant $m$ pièces, où chaque pièce est soit bleue, soit rouge. À son tour, Natalia peut choisir n'importe quelle pièce bleue et la retirer du jeu avec toutes les pièces situées au-dessus d'elle dans la pile. De même, à son tour, Cezary peut choisir n'importe quelle pièce rouge et la retirer avec toutes les pièces situées au-dessus d'elle dans la même pile. Les joueurs jouent à tour de rôle, et le perdant est celui qui ne peut pas effectuer de coup valide, c'est-à-dire lorsque toutes ses pièces ont déjà été retirées du jeu.

Connaissant les règles, ils doivent maintenant déterminer l'état initial du jeu : une suite de $d$ piles, chacune contenant exactement $m$ pièces. Ni Natalia ni Cezary ne veulent avoir un avantage injuste, ils ont donc convenu que la suite de piles doit être équitable. Une suite de piles est dite équitable si, en supposant que Natalia et Cezary jouent de manière optimale, le gagnant est le joueur qui ne joue pas le premier coup. Ainsi, si Natalia joue le premier coup, Cezary gagne avec une stratégie optimale, et vice versa : si Cezary commence, Natalia gagne.

Le couple a déjà disposé les $k$ premières piles de $m$ pièces chacune. Ils se demandent maintenant comment compléter cette suite de piles. Ils ont conclu qu'il n'est pas logique d'avoir plus de $n$ piles de pièces dans le jeu. Aidez-les et, pour chaque nombre $d$ dans l'intervalle $[k, n]$, indiquez combien il existe de suites équitables différentes de $d$ piles de $m$ pièces qui commencent par la suite de piles qu'ils ont déjà disposée. Deux suites de piles sont considérées comme différentes s'il existe $i \in [1, d]$ et $j \in [1, m]$ tels que la $j$-ième pièce de la $i$-ième pile soit bleue dans l'une des suites et rouge dans l'autre.

Comme ces résultats peuvent être très grands, il suffit de donner leurs restes modulo $10^9 + 7$.

Entrée

La première ligne de l'entrée standard contient trois entiers $n$, $m$ et $k$ ($1 \le n \le 32$; $1 \le m \le 24$; $0 \le k \le n$), représentant respectivement la limite sur le nombre de piles, le nombre de pièces dans chaque pile et le nombre de piles déjà créées.

Les $k$ lignes suivantes contiennent les descriptions des piles déjà placées ; la $i$-ième ligne contient une chaîne de caractères 'N' et 'C' de longueur exactement $m$, qui indique les couleurs des pièces dans la $i$-ième pile, en commençant par le bas. Si le $j$-ième caractère de cette chaîne est 'N', alors dans la $i$-ième pile, la $j$-ième pièce à partir du bas est bleue. Sinon, ce caractère est 'C', et la pièce est rouge.

Sortie

La seule ligne de sortie doit contenir une suite de $n - k + 1$ entiers, où le $i$-ième entier doit être le reste modulo $10^9 + 7$ du nombre de façons de prolonger la suite de $i - 1$ piles de sorte que la suite finale de piles soit équitable.

Exemples

Entrée 1

3 3 1
CCN

Sortie 1

0 1 3

Entrée 2

2 1 0

Sortie 2

1 0 2

Entrée 3

4 2 4
CN
NC
CC
NN

Sortie 3

1

Remarque

Dans le premier exemple, si nous n'ajoutons aucune pile, la suite à un élément ne sera pas équitable. Cependant, nous pouvons ajouter la pile NNC – une telle suite de deux piles sera équitable. Nous pouvons ajouter deux piles de trois manières : [CCN, NNN], [NNN, CCN], [NCN, NCN].

Sous-tâches

• Dans certains groupes de tests, la condition $k = n$ est vérifiée.
• Dans certains groupes de tests, les conditions $n \le 8$ et $m \le 8$ sont vérifiées.
• Dans certains groupes de tests, les conditions $n \le 12$ et $m \le 13$ sont vérifiées.
• Dans certains groupes de tests, la condition $n \le 16$ et $m \le 19$ est vérifiée.

Chaque cas mentionné ci-dessus décrit au moins un groupe non mentionné dans les cas précédents.