Fancy Arrays
Contest: Educational Codeforces Round 157 (Rated for Div. 2)
Difficulty rating: 2600
Tags: combinatorics, dp, math, matrices

Let's call an array $$$a$$$ of $$$n$$$ non-negative integers fancy if the following conditions hold:

- at least one from the numbers $$$x$$$, $$$x + 1$$$, ..., $$$x+k-1$$$ appears in the array;
- consecutive elements of the array differ by at most $$$k$$$ (i.e. $$$|a_i-a_{i-1}| \le k$$$ for each $$$i \in [2, n]$$$).

You are given $$$n$$$, $$$x$$$ and $$$k$$$. Your task is to calculate the number of fancy arrays of length $$$n$$$. Since the answer can be large, print it modulo $$$10^9+7$$$.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 50$$$) — the number of test cases.

The only line of each test case contains three integers $$$n$$$, $$$x$$$ and $$$k$$$ ($$$1 \le n, k \le 10^9$$$; $$$0 \le x \le 40$$$).

Output format:
For each test case, print a single integer — the number of fancy arrays of length $$$n$$$, taken modulo $$$10^9+7$$$.

Constraints:
Time limit: 4.0 s
Memory limit: 512.0 MB

Note:
In the first test case of the example, the following arrays are fancy:

- $$$[0, 0, 0]$$$;
- $$$[0, 0, 1]$$$;
- $$$[0, 1, 0]$$$;
- $$$[0, 1, 1]$$$;
- $$$[0, 1, 2]$$$;
- $$$[1, 0, 0]$$$;
- $$$[1, 0, 1]$$$;
- $$$[1, 1, 0]$$$;
- $$$[2, 1, 0]$$$.

Example input:
4
3 0 1
1 4 25
4 7 2
1000000000 40 1000000000

Example output:
9
25
582
514035484

Editorial:
It is difficult to directly calculate the number of arrays that satisfy both conditions. So let's calculate the opposite value — the number of arrays, where only the second condition is holds, and the first is necessarily violated.
Using the fact that the array can contain integers from two sets $$$[0, x)$$$ and $$$[x + k, \infty)$$$. We can notice that the array can consist of elements from only one set, but not both (because the difference between elements from different sets is at least $$$k+1$$$ which violates the second condition). So the answer to the problem is $$$f(0, M) - f(0, x-1) - f(x+k, M)$$$, where $$$f(l, r)$$$ is the number of arrays of length $$$n$$$ that satisfy the second condition and elements in range from $$$l$$$ to $$$r$$$, and $$$M$$$ is some big constant (let it be equal to $$$10^{100}$$$).
Let's take a closer look at the function $$$f(l, r)$$$. We can represent the required array $$$a$$$ as integer $$$a_1$$$ and an array of $$$n-1$$$ differences $$$\Delta_i=a_{i+1}-a_1$$$. There are $$$(2k+1)^{n-1}$$$ differences arrays in total, because of the second condition. Let $$$cnt(l, r, \Delta)$$$ be the number of valid $$$a_1$$$ for the given array $$$\Delta$$$ ($$$a_1$$$ is valid if it's produces array $$$a$$$, where all elements from $$$l$$$ to $$$r$$$). Using such a representation we can see that $$$f(l, r) = \sum\limits_{\Delta} cnt(l, r, \Delta)$$$. Moreover, let $$$mn$$$ be the minimum value in $$$\Delta$$$ and $$$mx$$$ be the maximum value in $$$\Delta$$$, then $$$cnt(l, r, \Delta)$$$ is equal to $$$\max(0, (r - l) - (mx - mn))$$$.
It is difficult to calculate the values of $$$f(0, M)$$$ and $$$f(x+k, M)$$$ independently, because we can't iterate over all arrays $$$\Delta$$$. Luckily, our goal is to calculate their difference. Since the value of $$$M$$$ is big enough, we can say that $$$cnt$$$ of any $$$\Delta$$$ is positive. So we can represent $$$f(0, M) - f(x+k, M)$$$ as $$$$$$\sum\limits_{\Delta} cnt(0, M, \Delta) - \sum\limits_{\Delta} cnt(x+k, M, \Delta)$$$$$$ or $$$$$$\sum\limits_{\Delta} (M - 0) - (mx - mn) - \sum\limits_{\Delta} (M - (x+k)) - (mx - mn))$$$$$$ Since the $$$\Delta$$$ arrays are the same in both cases, we can combine the sums $$$$$$\sum\limits_{\Delta} ((M - 0) - (mx - mn)) - ((M - (x + k)) - (mx - mn))$$$$$$ Let's expand the brackets, and we get the final value $$$$$$f(0, M) - f(x+k, M) = \sum\limits_{\Delta} x+k$$$$$$ We can see that each $$$\Delta$$$ array adds $$$x+k$$$ to the difference between two values. So this part of the answer is equal to the $$$(x+k)(2k+1)^{n-1}$$$.
It remains us to calculate the value of $$$f(0, x-1)$$$. We can do it using simple dynamic programming $$$dp_{i, j}$$$ — the number of arrays of length $$$i$$$ if the last element is $$$j$$$. The transition from $$$(i, y)$$$ to $$$(i + 1, z)$$$ can be made if $$$|y - z| \le k$$$. And the answer is equal to the sum of $$$dp_{n, j}$$$ for each $$$j \in [0, x)$$$ Such dynamic programming works in $$$O(nx)$$$, but $$$n$$$ is too big for this solution. However, thanks to fairly simple transitions, we can represent it as matrix multiplication. Using fast matrix exponentiation, we can calculate it in $$$O(x^3\log(n))$$$.
The total answer is $$$(x+k)(2k+1)^{n-1} - f(0, x - 1)$$$.