题解

题面描述

给定长度为 $n$ 的数组，每个位置填入来自 $1,2,\ldots,k$ 的整数。要求数组满足：
对于任意两个下标 $i$ 和 $j$，如果 $|i-j| \le c$，则有 $a_i \ne a_j$。
即任意连续的 $c+1$ 个元素必须互不相同。
求满足条件的数组构造方案总数，并将答案对 $10^9+7$ 取模后输出。

题目内容

你需要给长度为 $n$ 的数组填入整数，使得对于任意两个下标 $i$ 和 $j$ ,若满足：

• $|i-j|≤ c$ ;

那么这两个整数需要满足 $a_i≠ a_j$ 。

每一个元素必须从 $1,2,...,k$ 这 $k$ 个正整数中选择，求解有多少种不同的数组构造方案。由于答案可能很大，请将答案对 $(10^9+7)$ 取模后输出。

输入描述

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

在一行上输入三个整数 $n,k,c(1 ≤ n,k,c≤ 10^6)$ 代表数组的长度、可以选择的最大整数、下标限制。

输出描述

对于每一组测试数据，新起一行输出一个整数，代表不同的构造方案数量。由于答案可能很大，请将答案对 $(10^9+7)$ 取模后输出。

样例1

输入

2
3 3 2
2 5 6

输出

6
20

说明

合法的构造方案有 {$1,2,3$},{$1,3,2$},{$2,1,3$}{$2,3,1$},{$3,1,2$},{$3,2,1$}，一共有 $6$ 种。