解题思路

先说明一点：按题面原文“存在至少一个长度恰为 $m$ 的连续子段，且元素和不等于 $k$”严格推导时，给出的样例与题意并不一致。下面题解与代码均是按照题面原文来写的。

直接统计“至少一个子段和不等于 $k$”不好做，先求补集：

• 补集：所有长度恰为 $m$ 的连续子段，元素和都等于 $k$
• 答案就是$$$$

题目内容

给定四个整数 $n,v,m,k$，我们考虑长度为 $n$ 的序列 $a$ ，元素取值范围为 $1..v$，求满足以下性质的序列个数，对 $10^9+7$ 取模：

存在至少一个长度为 $m$ 的连续子段，其元素和不等于 $k$，保证 $m≤k$ 。

输入描述

每个测试文件均包含多组测试数据，第一行输入一个整数 $T(1≤T≤2×10^7)$ 代表数据组数，每组测试数据描述如下：

每行输入四个整数 $n,v,m,k (1≤n≤10^{18}，1≤v,m,k≤2×10^9)$ 并保证 $k≥m$。

保证所有测试中 $m$ 的总和不超过 $2×10^8$。

输出描述

输出 $T$ 行，每行一个整数，表示满足条件的序列个数对 $10^9+7$ 取模后的结果。

样例1

输入

4
1 1 2 2
3 2 2 3
4 3 3 6
10 3 3 6

输出

0
6
74
59042

说明

样例 $1$ ：$n=1,v=1,m=2,k=2$，由于 $n<m$，不存在长度为 $m$ 的子段，答案为 $0$ 。

样例 $2$ ：总数 $=2^3=8$，只有序列 $121$ 与 $212$ 是不可以的，因此答案 $=8−2=6$ 。