write a go solution for Description:
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|<=k for each iin[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<=t<=50) — the number of test cases.

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

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

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].. Output only the code with no comments, explanation, or additional text.