← 返回题目列表

Codeforces · 1895/F

F. 花式数组

中文机器翻译题面 查看原题

如果满足以下条件,我们将 $$$n$$$ 的数组 $$$a$$$ 称为非负整数:

- 数字 $$$x$$$、$$$x + 1$$$、...、$$$x+k-1$$$ 中至少有一个出现在数组中;
- 数组的连续元素最多相差 $$$k$$$ (即 $$$|a_i-a_{i-1}| \le k$$$ 对于 [2, n]$$$ 中的每个 $$$i \)。

您将获得 $$$n$$$、$$$x$$$ 和 $$$k$$$。你的任务是计算长度为 $$$n$$$ 的奇特数组的数量。由于答案可能很大,因此打印它对 $$$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$$$ 的奇特数组的数量,以 $$$10^9+7$$$ 为模。

示例

输入 #1

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

输出 #1

9
25
582
514035484

注意

在示例的第一个测试用例中,以下数组很奇特:

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