Пытаюсь решить задачку, закопался.

Вкратце, нужно найти количество N-значных чисел, у которых абсолютная разность между любыми двумя соседними цифрами не меньше K.
Ограничения: 2 ≤ N ≤ 10⁹, 0 ≤ K ≤ 9. Ответ нужно посчитать по модулю 10⁹ + 7.

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

Формулы получились следующие:
K = 9: F_i = F_i – 1 = 1 (ведущих нулей быть не должно, поэтому единственный возможный вариант 90909...)
K = 8: F_i = F_i – 1 + F_i – 2 (как Фибоначчи, только с другими начальными значениями, которые можно считать, например, перебором)
K = 7: F_i = 2·F_i – 1 + F_i – 2 – F_i – 3
K = 6: F_i = 2·F_i – 1 + 3·F_i – 2 – F_i – 3 – F_i – 4
K = 5: F_i = 3·F_i – 1 + 3·F_i – 2 – 4·F_i – 3 – F_i – 4 – F_i – 5

Далее становится чуть сложнее, например, при K = 4 от цифры 5 возможные варианты продолжения — 0, 1 и 9, и не очень понятно, как теперь меняется количество комбинаций.

Такое ощущение, что у этой задачи есть более простое решение, прошу поделиться или намекнуть.