题目描述
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输出。
30%数据
T=1
1 <= n <= 10
1 <= K <= 2
0 <= P < n
60%数据
T=1
1 <= n <= 50
1 <= K <= 10
0 <= P < n
100%数据
1 <= T <= 100
1 <= n <= 100
1 <= K <= 300
0 <= P < n
输入格式
第一行T,本题有T组数据。
接下来T行,每行三个整数,N,K,P.
输出格式
T行,每行一个答案
样例输入
样例输出