Natalia y Cezary disfrutan jugando juegos, especialmente aquellos que ellos mismos inventan. Decidieron organizar una secuencia de pilas de monedas, cada una con $m$ monedas, donde cada moneda es azul o roja. En su turno, Natalia puede elegir cualquier moneda azul y eliminarla del juego junto con todas las monedas que se encuentren encima de ella en la misma pila. De manera análoga, en su turno, Cezary puede elegir cualquier moneda roja y eliminarla junto con todas las monedas que se encuentren encima de ella en la misma pila. Los jugadores realizan sus movimientos por turnos, y pierde aquel que no pueda realizar un movimiento válido, es decir, cuando todas sus monedas ya han sido eliminadas del juego.

Conociendo las reglas, ahora deben establecer el estado inicial del juego: una secuencia de $d$ pilas, cada una conteniendo exactamente $m$ monedas. Ni Natalia ni Cezary quieren tener una ventaja injusta, por lo que acordaron que la secuencia de pilas debe ser justa. Una secuencia de pilas se denomina justa si, asumiendo que Natalia y Cezary juegan de manera óptima, el juego lo gana el jugador que no realiza el primer movimiento. Es decir, si Natalia realiza el primer movimiento, bajo una estrategia óptima ganará Cezary, y viceversa: si comienza Cezary, ganará Natalia.

La pareja ya ha organizado las primeras $k$ pilas de monedas, cada una con $m$ monedas. Ahora se preguntan cómo completar dicha secuencia de pilas. Han llegado a la conclusión de que no tiene sentido que haya más de $n$ pilas de monedas en el juego. Ayúdalos y, para cada número $d$ en el intervalo $[k, n]$, indica cuántas secuencias justas diferentes de $d$ pilas de $m$ monedas existen que comiencen con la secuencia de pilas que ya han organizado. Consideramos que dos secuencias de pilas son diferentes si existen $i \in [1, d]$ y $j \in [1, m]$ tales que la $j$-ésima moneda en la $i$-ésima pila es azul en una de las secuencias y roja en la otra.

Dado que estos resultados pueden ser muy grandes, basta con que proporciones sus restos al dividirlos por $10^9 + 7$.

Entrada

La primera línea de la entrada estándar contiene tres números enteros $n$, $m$ y $k$ ($1 \le n \le 32$; $1 \le m \le 24$; $0 \le k \le n$), que representan, respectivamente, el límite en el número de pilas, el número de monedas en cada pila y el número de pilas ya creadas.

Las siguientes $k$ líneas contienen las descripciones de las pilas ya establecidas; la $i$-ésima línea contiene una cadena de caracteres 'N' y 'C' de longitud exactamente $m$, que indica los colores de las monedas en la $i$-ésima pila, comenzando desde abajo. Si el $j$-ésimo carácter de esta cadena es 'N', entonces en la $i$-ésima pila la $j$-ésima moneda desde abajo es azul. De lo contrario, el carácter es 'C' y dicha moneda es roja.

Salida

En la única línea de salida debe aparecer una secuencia de $n - k + 1$ números enteros, donde el $i$-ésimo número debe ser el resto de la división por $10^9 + 7$ del número de formas en las que se puede extender la secuencia con $i - 1$ pilas de modo que la secuencia final de pilas sea justa.

Ejemplos

Entrada 1

3 3 1
CCN

Salida 1

0 1 3

Nota 1

En el primer caso de prueba, si no añadimos ninguna pila, la secuencia de un solo elemento no será justa. Sin embargo, podemos añadir la pila NNC; tal secuencia de dos pilas ya será justa. Podemos añadir dos pilas de tres formas: [CCN, NNN], [NNN, CCN], [NCN, NCN].

Entrada 2

2 1 0

Salida 2

1 0 2

Entrada 3

4 2 4
CN
NC
CC
NN

Salida 3

1

Subtareas

• En algunos grupos de pruebas se cumple la condición $k = n$.
• En algunos grupos de pruebas se cumplen las condiciones $n \le 8$ y $m \le 8$.
• En algunos grupos de pruebas se cumplen las condiciones $n \le 12$ y $m \le 13$.
• En algunos grupos de pruebas se cumple la condición $n \le 16$ y $m \le 19$.

Cada caso mencionado anteriormente describe al menos un grupo no mencionado en los casos anteriores.