CF1895F.Fancy Arrays

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]$ .