I'm trying to solve this problem but got stuck.

Briefly, we are asked to count N-digit numbers such that the absolute difference in the adjacent digits is greater than or equal to K.
Constraints: 2 ≤ N ≤ 10⁹, 0 ≤ K ≤ 9. Answer should be calculated modulo 10⁹ + 7.

I tried to derive some recurrence relations for the number of possible combinations of i digits, and then calculate the answer by matrix binary exponentiation technique.

Some first formulas are:
K = 9: F_i = F_i – 1 = 1 (no leading zeroes so the only option is 90909...)
K = 8: F_i = F_i – 1 + F_i – 2 (as Fibonacci but with different base values, which can be found using brute-force, for instance)
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

But then it becomes more complicated. For example, when K = 4 and current digit is 5, you can continue with 0, 1 и 9, so it isn't clear to me how the number of combinations changes now.

If there exists a simplier solution, please share it or just give a hint.