最大值

Description:

lqp在回忆自己初学OI的经历,他想起了自己学习如何找数组最大值的时候......

找到一个数组的最大值的一种方法是从数组开头对数组进行扫描,令max=a[0](数组下表从0..N-1),如果a_i>max,就更新max,这样就可以在O(N)的时间里找到一个数组的最大值。

这个问题是相当简单的,但是lqp想到了另一个问题,如果一个包含N个元素的数组a里面的元素的值是在1...K之间的整数,存在多少个不同的数组a,进行了如上扫描之后,max恰好进行了p次更新?

这个问题把lqp难住了,于是他想请你帮他算算。

下面是lqp手算的一组数据: 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}

共有6种情况
由于答案可能很大，lqp讨厌很大的数，所以你仅仅需要把答案mod 10^9+7输出。

Input:

第一行T,本题有T组数据。

接下来T行,每行三个整数,N,K,P.

Output:

T行,每行一个答案

Sample Input:

3
4 3 2
2 3 1
3 4 1

Sample Output:

6
3
30

Note:

 

本题由旧版NOJ导入，来源：JSOI2010