Você tem uma string longa $S$ de M e O e um inteiro $K \geq 1$. Conte as decomposições em subsequências MOOOO....O, cada uma com exatamente $K$ letras O, módulo $10^9+7$.

Por ser longa, ela não é dada explicitamente. São dados $L$ ($1 \leq L \leq 10^{18}$) e uma string $T$ de comprimento $N$ ($1 \leq N \leq 10^6$). $S$ concatena $L$ cópias de $T$.

Entrada

A primeira linha contém $K$, $N$ e $L$.

A segunda contém $T$ de comprimento $N$, com cada caractere M ou O.

É garantido que o número de decomposições de $S$ não é zero.

Saída

Imprima o número de decomposições de $S$ módulo $10^9+7$.

Exemplos

Entrada 1

2 6 1
MOOMOO

Saída 1

1

Nota

A única decomposição em MOO usa os três primeiros caracteres para um e os três últimos para outro.

Entrada 2

2 6 1
MMOOOO

Saída 2

6

Nota

Há seis decomposições distintas em subsequências (as maiúsculas formam um MOO, as minúsculas outro):

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

Entrada 3

1 4 2
MMOO

Saída 3

4

Entrada 4

1 4 100
MMOO

Saída 4

976371285

Nota

Lembre-se de tomar a resposta módulo $10^9+7$.

Subtarefas

• Testes 5–7: $K=1$, $L = 1$
• Testes 8–10: $K=2$, $N\leq 1000$, $L = 1$
• Testes 11–13: $K=1$
• Testes 14–19: $L = 1$
• Testes 20–25: Sem restrições adicionais.

Créditos do problema: Dhruv Rohatgi