Дана длинная строка $S$ из M и O и целое $K \geq 1$. Посчитайте способы разложить $S$ на подпоследовательности MOOOO....O, каждая ровно с $K$ буквами O, по модулю $10^9+7$.

Строка длинная и явно не дана. Вместо неё даны $L$ ($1 \leq L \leq 10^{18}$) и строка $T$ длины $N$ ($1 \leq N \leq 10^6$). $S$ — конкатенация $L$ копий $T$.

Входные данные

Первая строка содержит $K$, $N$ и $L$.

Вторая содержит строку $T$ длины $N$; каждый символ — M или O.

Гарантируется, что число разложений $S$ ненулевое.

Выходные данные

Выведите число разложений $S$ по модулю $10^9+7$.

Примеры

Входные данные 1

2 6 1
MOOMOO

Выходные данные 1

1

Примечание

Единственный способ разбить $S$ на MOO — первые три символа образуют один MOO, последние три — другой.

Входные данные 2

2 6 1
MMOOOO

Выходные данные 2

6

Примечание

Есть шесть различных разложений на подпоследовательности (прописные буквы образуют один MOO, строчные — другой):

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

Входные данные 3

1 4 2
MMOO

Выходные данные 3

4

Входные данные 4

1 4 100
MMOO

Выходные данные 4

976371285

Примечание

Не забудьте взять ответ по модулю $10^9+7$.

Подзадачи

• Тесты 5–7: $K=1$, $L = 1$
• Тесты 8–10: $K=2$, $N\leq 1000$, $L = 1$
• Тесты 11–13: $K=1$
• Тесты 14–19: $L = 1$
• Тесты 20–25: Без дополнительных ограничений.

Автор задачи: Dhruv Rohatgi