SP5969 FINDMAX - Finding Maximum

一种找出数组中最大元素的方法是：首先将一个变量初始化为数组的第一个元素，然后遍历数组的剩余部分，遇到比该变量严格更大的值时，就更新该变量。这道题告诉我们：如果一个数组有 $N$ 个元素，每个元素的值都在 $1$ 到 $K$ 之间，那么有多少种这样的数组，能够使得上述算法恰好进行 $P$ 次更新？注意，变量的初始化不算作一次更新。 举个例子，当 $N = 4$, $K = 3$, $P = 2$ 时，满足条件的数组有： 1) {1, 1, 2, 3} 2) {1, 2, 1, 3} 3) {1, 2, 2, 3} 4) {1, 2, 3, 1} 5) {1, 2, 3, 2} 6) {1, 2, 3, 3}

第一行是一个整数 $T$，表示测试用例的数量。接下来的 $T$ 行中，每行包含三个整数，分别是 $N$、$K$ 和 $P$，用空格隔开。

对于每个测试用例，输出一行结果。因为结果可能会非常大，请输出对 $1000000007$ 取模后的结果。 ## 数据范围 - $1 \leq T \leq 100$ - $1 \leq N, K, P \leq 1000$ **本翻译由 AI 自动生成**