На занятии по иностранному языку преподаватель раздал студентам небольшие тексты, сообщив, что это фрагменты статей из научно-популярных журналов, и предложил в течение нескольких минут подготовить очень короткое изложение содержания этих фрагментов.
Фалалей хотел воспользоваться онлайн-переводчиком, но к его огорчению, в этом крыле университета мобильный интернет практически отсутствовал. Немного поразмышляв о том, что уже сейчас необходимости в знании иностранного языка попросту нет, Фалалей решил в своем изложении сказать, что предложенный ему текст повествует о больших языковых моделях. Во всяком случае, он готов отыскать в этом тексте много упоминаний о таких моделях.
Фалалей утверждает, что если после вычеркивания из текста некоторых символов оставшиеся будут представлять собой последовательность $$$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$$$ — длина последовательности) | |||
| 1 | 2 (до 10) | $$$n \le 20$$$ | нет | полная |
| 2 | 2 (до 20) | $$$n \le 1000, \, k = 1$$$ | нет | полная |
| 3 | 0 (30) | $$$k \ge n/2$$$ | 1, 2 | первая ошибка |
| 4 | 0 (40) | любые допустимые значения | 1, 2, 3 | первая ошибка |
3alblmdllmleltle
12
3alaaaalmlbbbbbblb
0
25alaaaalmlbbbbbblb
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.
| Name |
|---|


