Ctrl K

Залипающие клавиши

Сложная
У клавиатуры залипают клавиши: при нажатии буква иногда печатается не один раз, а несколько подряд. Пропускать буквы клавиатура не умеет. На экране получилась строка screen. Известно, что человек хотел набрать слово длиной не меньше min_len. Сколько существует различных слов, которые он мог иметь в виду? Ответ может быть большим, верните его по модулю 10⁹ + 7.
Пример 1
screen="aabbb", min_len=3 → 5

Из серии "aa" могла остаться 1 или 2 буквы, из "bbb" — от 1 до 3: всего 2 · 3 = 6 вариантов. Короче 3 только "ab", значит, ответ 5.

Пример 2
screen="xyz", min_len=2 → 1

Повторов нет, так что исходное слово могло быть только "xyz".

Пример 3
screen="ooo", min_len=4 → 0

Исходное слово не длиннее того, что на экране, а здесь всего 3 буквы.

Ограничения
  • 1 ≤ len(screen) ≤ 5 · 10⁵
  • screen состоит из строчных латинских букв
  • 1 ≤ min_len ≤ 2000
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиРасстановки по подъёмам и спускам СложнаяКовры на белой плитке СложнаяПрыжки по целым плиткам СредняяПроверка трёх зданий СредняяШаблон с точкой и звёздочкой Сложная
загружаем Python…
Вход
screen="aabbb", min_len=3
Ожидается
5

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 106 тестов на сервере, включая скрытые.