310830: CF1895F. Fancy Arrays

F. Fancy Arraystime limit per test4 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

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

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

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

ExampleInput

4
3 0 1
1 4 25
4 7 2
1000000000 40 1000000000

Output

9
25
582
514035484

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

题目大意：
定义一个非负整数数组a为“花哨”（fancy），如果满足以下条件：
- 数组中至少包含一个数x, x+1, ..., x+k-1；
- 数组中相邻元素之差最多为k（即对于每个i ∈ [2, n]，有|a_i - a_(i-1)| ≤ k）。

给定n, x和k，任务是计算长度为n的“花哨”数组的数量。由于答案可能很大，结果需要模上10^9+7。

输入数据格式：
第一行包含一个整数t（1 ≤ t ≤ 50）——测试用例的数量。
每个测试用例包含一行，有三个整数n, x和k（1 ≤ n, k ≤ 10^9; 0 ≤ x ≤ 40）。

输出数据格式：
对于每个测试用例，输出一个整数——长度为n的“花哨”数组的数量，模上10^9+7。题目大意： 定义一个非负整数数组a为“花哨”（fancy），如果满足以下条件： - 数组中至少包含一个数x, x+1, ..., x+k-1； - 数组中相邻元素之差最多为k（即对于每个i ∈ [2, n]，有|a_i - a_(i-1)| ≤ k）。 给定n, x和k，任务是计算长度为n的“花哨”数组的数量。由于答案可能很大，结果需要模上10^9+7。 输入数据格式： 第一行包含一个整数t（1 ≤ t ≤ 50）——测试用例的数量。 每个测试用例包含一行，有三个整数n, x和k（1 ≤ n, k ≤ 10^9; 0 ≤ x ≤ 40）。 输出数据格式： 对于每个测试用例，输出一个整数——长度为n的“花哨”数组的数量，模上10^9+7。