题目内容

花坛中有 $n$ 个位置排成一行，依次编号为 $1$ 到 $n$。你需要在每个位置种植一种花卉，可供选择的花卉种类编号为 $1$ 到 $k$。为了保证视觉效果，要求任意两个距离不超过 $c$ 的位置（即满足 $|i-j| \le c$ 的位置 $i$ 和 $j$）不能种植相同种类的花卉。请计算共有多少种不同的种植方案。由于答案可能很大，请将结果对 $10^9+7$ 取模后输出。

数据范围：测试数据组数 $T$ 不超过 $2 \times 10^5$；对于每组数据，$n$、$k$、$c$ 均为不超过 $10^6$ 的正整数。

输入描述

第一行包含一个整数 $T$，表示测试数据组数。接下来 $T$ 行，每行包含三个整数，依次表示 $n$、$k$、$c$。