Конь на телефонной клавиатуре

Средняя

Цифры на телефонной клавиатуре расположены так:

На одну из клавиш ставят шахматного коня. Конь ходит буквой «Г»: на две клетки по вертикали и одну по горизонтали или на две по горизонтали и одну по вертикали. Вставать можно только на клавиши с цифрами, пустых клеток слева и справа от 0 нет. Клавиша, с которой конь начал, — первая цифра номера, каждая следующая клавиша после хода добавляет к номеру ещё одну цифру. Сколько различных номеров длины length можно так набрать (ровно length - 1 ходов, начать можно с любой клавиши)? Ответ может быть очень большим — верните его по модулю 10⁹ + 7.

Пример 1

length=1 → 10

Номер из одной цифры — просто клавиша, на которую поставили коня: 10 вариантов.

Пример 2

length=2 → 20

Ходы: 0→4, 0→6, 1→6, 1→8, 2→7, 2→9, 3→4, 3→8, 4→0, 4→3, 4→9, 6→0, 6→1, 6→7, 7→2, 7→6, 8→1, 8→3, 9→2, 9→4 — всего 20. С клавиши 5 конь никуда не прыгнет.

Пример 3

length=4 → 104

Ограничения

1 ≤ length ≤ 5000

Встречал эту задачу на настоящем собесе?

Решили0

Пробовали0

Отправок0

Принято—

Темы

Dynamic Programming

Вход

length=1

Ожидается

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