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

我们称一个由 $n$ 个非负整数组成的数组 $a$ 是“精巧的”（fancy），当且仅当满足以下两个条件：

• 数 $x$, $x + 1$, ..., $x+k-1$ 中至少有一个出现在该数组中；
• 数组中相邻元素之差的绝对值至多为 $k$（即对每个 $i \in [2, n]$，均有 $|a_i-a_{i-1}| \le k$）。

给定 $n$、$x$ 和 $k$，你的任务是计算长度为 $n$ 的精巧数组的个数。由于答案可能很大，请输出其对 $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$).

第一行包含一个整数 $t$（$1 \le t \le 50$）—— 测试用例的数量。

每个测试用例仅有一行，包含三个整数 $n$、$x$ 和 $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$.

对于每个测试用例，输出一个整数——长度为 $n$ 的“炫酷数组”（fancy arrays）的个数，对 $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]$.

在示例的第一个测试用例中，以下数组是“花哨的”（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]$。