D. От L до L и до M и обратно
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

На занятии по иностранному языку преподаватель раздал студентам небольшие тексты, сообщив, что это фрагменты статей из научно-популярных журналов, и предложил в течение нескольких минут подготовить очень короткое изложение содержания этих фрагментов.

Фалалей хотел воспользоваться онлайн-переводчиком, но к его огорчению, в этом крыле университета мобильный интернет практически отсутствовал. Немного поразмышляв о том, что уже сейчас необходимости в знании иностранного языка попросту нет, Фалалей решил в своем изложении сказать, что предложенный ему текст повествует о больших языковых моделях. Во всяком случае, он готов отыскать в этом тексте много упоминаний о таких моделях.

Фалалей утверждает, что если после вычеркивания из текста некоторых символов оставшиеся будут представлять собой последовательность $$$llmll$$$, то это и есть упоминание о большой языковой модели. Впрочем, он готов согласиться, что количество вычеркнутых символов между каждой из крайних букв $$$l$$$ и буквой $$$m$$$ не должно превосходить $$$k$$$.

Ваша задача — определить количество таких упоминаний в заданном тексте. Количество таких упоминаний может быть очень большим, поэтому ответ следует выводить по модулю $$$10^9 + 7$$$.

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

В первой строке содержится число $$$k$$$ $$$(1 \le k \le 2 \cdot 10^5)$$$ — максимально допустимое количество вычеркнутых символов между крайней буквой $$$l$$$ и буквой $$$m$$$.

Во второй строке содержится последовательность строчных латинских букв без пробелов. Длина последовательности не превосходит $$$2 \cdot 10^5$$$. Гарантируется, что в последовательности содержится хотя бы одна буква $$$m$$$.

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

Выведите одно целое число — количество упоминаний $$$llmll$$$ в тексте. Поскольку количество таких упоминаний может быть очень большим, выводите это число по модулю $$$10^9 + 7$$$.

Система оценки

В первых двух подзадачах применяется потестовая система оценки. В графе «Баллы» указано количество баллов за тест и в скобках максимальное количество баллов, которое можно набрать за подзадачу. Участнику сообщаются номера тестов подзадачи, которые не были пройдены.

В третьей и четвёртой подзадачах баллы начисляются только в случае прохождения всех тестов этой подзадачи. Участнику сообщается либо номер первого непройденного теста и результат проверки на этом тесте, либо что все тесты подзадачи пройдены.

Для третьей и четвёртой подзадач требуется, чтобы программа верно решала предшествующие подзадачи. Более подробно разбиение на подзадачи показано в таблице ниже.

ПодзадачаБаллы за тестОграниченияНеобходимыеИнформация
(баллыподзадачио проверке
за подзадачу)($$$n$$$ — длина последовательности)
12 (до 10)$$$n \le 20$$$нетполная
22 (до 20)$$$n \le 1000, \, k = 1$$$нетполная
30 (30)$$$k \ge n/2$$$1, 2первая ошибка
40 (40)любые допустимые значения1, 2, 3первая ошибка

Примеры
Входные данные
3
alblmdllmleltle
Выходные данные
12
Входные данные
3
alaaaalmlbbbbbblb
Выходные данные
0
Входные данные
25
alaaaalmlbbbbbblb
Выходные данные
1
Примечание

Поясним приведённые примеры.

Для облегчения восприятия запишем буквы через пробел и будем выделять жирным шрифтом те, которые будут входить в очередное упоминание.

В первом примере упоминания будут следующие:

a l b l m d l l m l e l t l e

a l b l m d l l m l e l t l e

a l b l m d l l m l e l t l e

a l b l m d l l m l e l t l e

a l b l m d l l m l e l t l e

a l b l m d l l m l e l t l e

a l b l m d l l m l e l t l e

a l b l m d l l m l e l t l e

a l b l m d l l m l e l t l e

a l b l m d l l m l e l t l e

a l b l m d l l m l e l t l e

a l b l m d l l m l e l t l e

Во втором примере вычеркнуть не более 3 символов с каждой стороны от буквы $$$m$$$ недостаточно, чтобы получить хотя бы одно упоминание, поэтому ответ 0.

В третьем примере $$$k$$$ превосходит длину строки, поэтому, в отличие от предыдущего примера, можно вычеркнуть четыре буквы a слева и шесть букв b справа, чтобы получить llmll.