Vous avez une longue chaîne $S$ de M et de O et un entier $K \geq 1$. Comptez ses décompositions en sous-séquences MOOOO....O, chacune avec exactement $K$ lettres O, modulo $10^9+7$.

Trop longue, elle n’est pas donnée explicitement. Vous recevez $L$ ($1 \leq L \leq 10^{18}$) et une chaîne $T$ de longueur $N$ ($1 \leq N \leq 10^6$). $S$ est la concaténation de $L$ copies de $T$.

Entrée

La première ligne contient $K$, $N$ et $L$.

La deuxième contient $T$ de longueur $N$, chaque caractère étant M ou O.

Le nombre de décompositions de $S$ est garanti non nul.

Sortie

Affichez le nombre de décompositions de $S$, modulo $10^9+7$.

Exemples

Entrée 1

2 6 1
MOOMOO

Sortie 1

1

Remarque

La seule décomposition en MOO fait des trois premiers caractères un MOO et des trois derniers un autre.

Entrée 2

2 6 1
MMOOOO

Sortie 2

6

Remarque

Il existe six décompositions distinctes en sous-séquences (les majuscules forment un MOO, les minuscules un autre) :

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

Entrée 3

1 4 2
MMOO

Sortie 3

4

Entrée 4

1 4 100
MMOO

Sortie 4

976371285

Remarque

Prenez bien la réponse modulo $10^9+7$.

Sous-tâches

• Tests 5–7: $K=1$, $L = 1$
• Tests 8–10: $K=2$, $N\leq 1000$, $L = 1$
• Tests 11–13: $K=1$
• Tests 14–19: $L = 1$
• Tests 20–25: Aucune contrainte supplémentaire.

Crédits du problème : Dhruv Rohatgi