Masz długi napis $S$ z M i O oraz liczbę całkowitą $K \geq 1$. Policz rozkłady na podciągi MOOOO....O, każdy z dokładnie $K$ literami O, modulo $10^9+7$.

Napis jest za długi na jawne podanie. Dostajesz $L$ ($1 \leq L \leq 10^{18}$) i napis $T$ długości $N$ ($1 \leq N \leq 10^6$). $S$ jest połączeniem $L$ kopii $T$.

Wejście

Pierwszy wiersz zawiera $K$, $N$ i $L$.

Drugi zawiera $T$ długości $N$, każdy znak to M lub O.

Liczba rozkładów $S$ jest gwarantowana niezerowa.

Wyjście

Wypisz liczbę rozkładów $S$ modulo $10^9+7$.

Przykład

Wejście 1

2 6 1
MOOMOO

Wyjście 1

1

Uwagi

Jedyny rozkład na MOO tworzy jedno z pierwszych trzech znaków, a drugie z ostatnich trzech.

Wejście 2

2 6 1
MMOOOO

Wyjście 2

6

Uwagi

Istnieje sześć różnych rozkładów na podciągi (wielkie litery tworzą jedno MOO, małe drugie):

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

Wejście 3

1 4 2
MMOO

Wyjście 3

4

Wejście 4

1 4 100
MMOO

Wyjście 4

976371285

Uwagi

Pamiętaj o wyniku modulo $10^9+7$.

Podzadania

• Testy 5–7: $K=1$, $L = 1$
• Testy 8–10: $K=2$, $N\leq 1000$, $L = 1$
• Testy 11–13: $K=1$
• Testy 14–19: $L = 1$
• Testy 20–25: Bez dodatkowych ograniczeń.

Autor zadania: Dhruv Rohatgi