F. Fancy Arrays
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\).
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\)).
For each test case, print a single integer — the number of fancy arrays of length \(n\), taken modulo \(10^9+7\).
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]\).