华丽数组

• 时间限制：5 秒
• 内存限制：512 MiB

题目描述

称一个长度为 $n$ 的非负整数数组 $a$ 为“华丽数组”，当且仅当它同时满足：

• 数组中至少有一个数属于 $[x,x+k-1]$；
• 对每个 $2\le i\le n$，均有 $|a_i-a_{i-1}|\le k$。

给定 $n,x,k$，求长度为 $n$ 的华丽数组数量。答案对 $10^9+7$ 取模。

输入格式

第一行一个整数 $t$，表示测试用例数。

接下来 $t$ 行，每行三个整数 $n,x,k$。

输出格式

对每个测试用例输出一行一个整数，表示答案对 $10^9+7$ 取模后的结果。

样例输入

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

样例输出

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

数据范围

对所有数据，满足：

• $1\le t\le50$；
• $1\le n,k\le10^9$；
• $0\le x\le40$。

子任务编号	分值	特殊限制
1	20	每个 $n\le5$、$k\le2$、$x\le3$，且 $\sum n\le30$
2	40	每个 $n\le5000$，且 $\sum n\le5000$
3		无特殊限制