CF1895F Fancy Arrays

我们称一个长度为 $n$ 的非负整数数组 $a$ 为“fancy”，如果满足以下条件： - 数组中至少出现了 $x, x+1, \ldots, x+k-1$ 中的某一个数； - 数组中相邻元素的差的绝对值不超过 $k$（即对于每个 $i \in [2, n]$，都有 $|a_i - a_{i-1}| \le k$）。 给定 $n$、$x$ 和 $k$，你的任务是计算长度为 $n$ 的“fancy”数组的数量。由于答案可能很大，请输出对 $10^9+7$ 取模后的结果。

第一行包含一个整数 $t$（$1 \le t \le 50$），表示测试用例的数量。 每个测试用例占一行，包含三个整数 $n$、$x$ 和 $k$（$1 \le n, k \le 10^9$；$0 \le x \le 40$）。

对于每个测试用例，输出一个整数，表示长度为 $n$ 的“fancy”数组的数量，对 $10^9+7$ 取模。

在示例的第一个测试用例中，以下数组是“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]$。 由 ChatGPT 4.1 翻译