如果满足以下条件,我们将 $$$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]$$$.