Вам дана длинная строка \(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\).
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка содержит
\(K\),
\(N\),
\(L\).
Вторая строка содержит строку \(T\) длины \(N\). Каждый символ или M или O.
Гарантируется, что количество декомпозиций \(S\) не равно 0.
ФОРМАТ ВВОДА (на экран / stdout):
Выведите количество разбиений строки \(S\), по модулю modulo \(10^9+7\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 6 1
MOOMOO
|
1
|