#2699. 更新

内存限制:128 MiB 时间限制:10 Sec

题目描述

       对于一个数列A[1..N],一种寻找最大值的方法是:依次枚举A[2]到A[N],如果A[i]比当前的A[1]值要大,那么就令A[1]=A[i],最后A[1]为所求最大值。假设所有数都在范围[1, K]内,按上面的步骤执行,有多少个长度N的数列满足A[1]被更新的次数恰好为P呢?
 

输入格式

       本题有多组数据。输入第一行一个数T为数据组数,下面T行每行依次三个数N、K和P。

输出格式

       对每组数据输出一行,为方案数模1000000007的值。
 

输入
输出
解释
3
4 3 2
2 3 1
3 4 1
6
3
30
对第一组数据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}

 
数据范围
       前20%的数据满足T ≤ 5
前50%的数据满足1 ≤ N ≤ 50,1 ≤ K ≤ 100
       对100%的数据,T ≤ 1000,1 ≤ N ≤ 150,0 ≤ P < N,1 ≤ K ≤ 300

样例

样例输入


			

样例输出


			

数据范围与提示