题目内容

给定四个参数 $L, U, W, S$，考虑所有长度为 $L$ 的整数数组，每个元素均在 $1$ 到 $U$ 之间取值。对于一个连续的长度为 $W$ 的子数组，如果它的元素之和恰好等于 $S$，则称该子数组是平衡的。现要求统计至少存在一个长度为 $W$ 的连续子数组不是平衡的数组数量。答案对 $10^9+7$ 取模。

数据范围：$1 \le L \le 10^{18}$，$1 \le U, W, S \le 2 imes 10^9$，且保证 $W \le S$。测试组数 $T$ 满足 $1 \le T \le 2 imes 10^7$，所有测试数据中 $W$ 的总和不超过 $2 imes 10^8$。

输入描述

第一行包含一个整数 $T$，表示测试数据组数。接下来 $T$ 行，每行包含四个用空格分隔的整数 $L, U, W, S$，分别表示数组长度、元素取值范围上限、窗口长度、目标值。各参数满足上述数据范围。

输出描述

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

样例1

输入

1
2 5 3 10

输出

0

说明

数组长度 $L = 2$，窗口长度 $W = 3$。由于 $L < W$，数组中不存在任何长度为 $W$ 的连续子数组，因此不存在“不是平衡的”子数组，满足条件的数组数量为 0。

样例2

输入

1
3 4 1 2

输出

63

说明

$L = 3$，$U = 4$，$W = 1$，$S = 2$。

总数组数量为 $4^3 = 64$。

当 $W = 1$ 时，平衡子数组即单个元素等于 2。如果所有长度为 1 的子数组都是平衡的，意味着数组中每一个元素都必须等于 2，这样的数组只有唯一一个：$[2,2,2]$。

因此，至少存在一个长度为 1 的子数组不是平衡的数组数量为 $64 - 1 = 63$。

样例3

输入

1
4 4 3 6

输出

246

说明

$L = 4$，$U = 4$，$W = 3$，$S = 6$。

总数组数为 $4^4 = 256$。

若所有长度为 3 的连续子数组和都等于 6，则前 $W = 3$ 个元素的和必须为 $S = 6$，且整个数组由前 $3$ 个元素周期性延拓（因为 $a_{i+W} = a_i$）。因此只需统计长度为 3、每个元素在 $[1, 4]$ 内、总和为 6 的序列个数。

求解 $x_1 + x_2 + x_3 = 6$，$1 \le x_i \le 4$。枚举可得：$(1,1,4)$ 及其排列共 3 种；$(1,2,3)$ 及其排列共 6 种；$(2,2,2)$ 共 1 种。合计 $3 + 6 + 1 = 10$ 种。

因此答案为 $256 - 10 = 246$。

样例4

输入

1
3 2 3 4

输出

5

说明

$L = 3$，$U = 2$，$W = 3$，$S = 4$。

总数组数 $2^3 = 8$。此时 $L = W$，整个数组即为唯一的长度为 $3$ 的窗口。所有窗口都是平衡的等价于数组总和恰好为 $4$。

元素在 $[1, 2]$ 内，总和为 4 的长度为 3 的序列只有 $(1,1,2)$ 的排列，共 3 种。因此答案为 $8 - 3 = 5$。