Hai una stringa lunga $S$ di M e O e un intero $K \geq 1$. Conta le scomposizioni in sottosequenze MOOOO....O, ciascuna con esattamente $K$ lettere O, modulo $10^9+7$.

Poiché è lunga, non è data esplicitamente. Ricevi $L$ ($1 \leq L \leq 10^{18}$) e una stringa $T$ di lunghezza $N$ ($1 \leq N \leq 10^6$). $S$ concatena $L$ copie di $T$.

Input

La prima riga contiene $K$, $N$ e $L$.

La seconda contiene $T$ di lunghezza $N$, ogni carattere M oppure O.

Il numero di scomposizioni di $S$ è garantito diverso da zero.

Output

Stampate il numero di scomposizioni di $S$ modulo $10^9+7$.

Esempi

Input 1

2 6 1
MOOMOO

Output 1

1

Nota

L’unica scomposizione in MOO usa i primi tre caratteri per uno e gli ultimi tre per un altro.

Input 2

2 6 1
MMOOOO

Output 2

6

Nota

Ci sono sei scomposizioni distinte in sottosequenze (le maiuscole formano un MOO, le minuscole un altro):

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

Input 3

1 4 2
MMOO

Output 3

4

Input 4

1 4 100
MMOO

Output 4

976371285

Nota

Assicuratevi di prendere la risposta modulo $10^9+7$.

Sottoproblemi

• Test 5–7: $K=1$, $L = 1$
• Test 8–10: $K=2$, $N\leq 1000$, $L = 1$
• Test 11–13: $K=1$
• Test 14–19: $L = 1$
• Test 20–25: Nessun vincolo aggiuntivo.

Crediti del problema: Dhruv Rohatgi