Du hast eine lange Zeichenkette $S$ aus M und O und ein ganzzahliges $K \geq 1$. Zähle ihre Zerlegungen in Teilfolgen MOOOO....O mit je genau $K$ Buchstaben O, modulo $10^9+7$.

Sie ist zu lang für eine explizite Angabe. Stattdessen erhältst du $L$ ($1 \leq L \leq 10^{18}$) und $T$ der Länge $N$ ($1 \leq N \leq 10^6$). $S$ ist die Verkettung von $L$ Kopien von $T$.

Eingabe

Die erste Zeile enthält $K$, $N$ und $L$.

Die zweite enthält $T$ der Länge $N$; jedes Zeichen ist M oder O.

Die Anzahl der Zerlegungen von $S$ ist garantiert ungleich null.

Ausgabe

Gib die Anzahl der Zerlegungen von $S$ modulo $10^9+7$ aus.

Beispiele

Eingabe 1

2 6 1
MOOMOO

Ausgabe 1

1

Hinweis

Die einzige Zerlegung in MOO macht aus den ersten drei Zeichen ein MOO und aus den letzten drei ein weiteres.

Eingabe 2

2 6 1
MMOOOO

Ausgabe 2

6

Hinweis

Es gibt sechs verschiedene Zerlegungen in Teilfolgen (Großbuchstaben bilden ein MOO, Kleinbuchstaben ein anderes):

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

Eingabe 3

1 4 2
MMOO

Ausgabe 3

4

Eingabe 4

1 4 100
MMOO

Ausgabe 4

976371285

Hinweis

Nimm die Antwort unbedingt modulo $10^9+7$.

Teilaufgaben

• 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: Keine zusätzlichen Einschränkungen.

Aufgabenautor: Dhruv Rohatgi