解题思路
先说明一点：按题面原文“存在至少一个长度恰为 m 的连续子段，且元素和不等于 k”严格推导时，给出的样例与题意并不一致。下面题解与代码均是按照题面原文来写的。
直接统计“至少一个子段和不等于 k”不好做，先求补集：
- 补集：所有长度恰为 m 的连续子段，元素和都等于 k
- 答案就是
P4756.第3题-数序列(二)
题目内容
给定四个整数 n,v,m,k，我们考虑长度为 n 的序列 a ，元素取值范围为 1..v，求满足以下性质的序列个数，对 109+7 取模：
存在至少一个长度为 m 的连续子段，其元素和不等于 k，保证 m≤k 。
输入描述
每个测试文件均包含多组测试数据，第一行输入一个整数 T(1≤T≤2×107) 代表数据组数，每组测试数据描述如下：
每行输入四个整数 n,v,m,k(1≤n≤1018，1≤v,m,k≤2×109) 并保证 k≥m。
保证所有测试中 m 的总和不超过 2×108。
输出描述
输出 T 行，每行一个整数，表示满足条件的序列个数对 109+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 ：总数 =23=8，只有序列 121 与 212 是不可以的，因此答案 =8−2=6 。
