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.

Hello!
I'm trying to solve the following problem:

Two strings can be shuffled by interleaving their letters to form a new string (original order of letters is preserved). We will consider a shuffle of two identical strings (twins).

For instance, the string AAABAB can be obtained by shuffling two strings AAB.

For a given string we should check if it can be obtained by shuffling two twins.

At first, we should check the parity of each letter (XOR of all letters == 0).
Next, i can't think up anything except brute-force solution with complexity O(2^N) :(

Is there a way to solve the problem efficiently? Thanks!