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 ≤ 109, 0 ≤ K ≤ 9. Answer should be calculated modulo 109 + 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: Fi = Fi – 1 = 1 (no leading zeroes so the only option is 90909...)
K = 8: Fi = Fi – 1 + Fi – 2 (as Fibonacci but with different base values, which can be found using brute-force, for instance)
K = 7: Fi = 2·Fi – 1 + Fi – 2 – Fi – 3
K = 6: Fi = 2·Fi – 1 + 3·Fi – 2 – Fi – 3 – Fi – 4
K = 5: Fi = 3·Fi – 1 + 3·Fi – 2 – 4·Fi – 3 – Fi – 4 – Fi – 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.