Tienes una cadena larga $S$ de M y O y un entero $K \geq 1$. Cuenta sus descomposiciones en subsecuencias MOOOO....O, cada una con exactamente $K$ letras O, módulo $10^9+7$.

Como es muy larga no se da explícitamente. Recibes $L$ ($1 \leq L \leq 10^{18}$) y una cadena $T$ de longitud $N$ ($1 \leq N \leq 10^6$). $S$ concatena $L$ copias de $T$.

Entrada

La primera línea contiene $K$, $N$ y $L$.

La segunda contiene $T$ de longitud $N$, con cada carácter M u O.

Se garantiza que el número de descomposiciones de $S$ no es cero.

Salida

Imprime el número de descomposiciones de $S$ módulo $10^9+7$.

Ejemplos

Entrada 1

2 6 1
MOOMOO

Salida 1

1

Nota

La única descomposición en MOO usa los tres primeros caracteres como uno y los tres últimos como otro.

Entrada 2

2 6 1
MMOOOO

Salida 2

6

Nota

Hay seis descomposiciones distintas en subsecuencias (las mayúsculas forman un MOO, las minúsculas otro):

• MmOOoo
• MmOoOo
• MmOooO
• MmoOOo
• MmoOoO
• MmooOO

Entrada 3

1 4 2
MMOO

Salida 3

4

Entrada 4

1 4 100
MMOO

Salida 4

976371285

Nota

Asegúrate de tomar la respuesta módulo $10^9+7$.

Subtareas

• Pruebas 5–7: $K=1$, $L = 1$
• Pruebas 8–10: $K=2$, $N\leq 1000$, $L = 1$
• Pruebas 11–13: $K=1$
• Pruebas 14–19: $L = 1$
• Pruebas 20–25: Sin restricciones adicionales.

Créditos del problema: Dhruv Rohatgi