题目描述

对于一个数列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 16 3 30对第一组数据N=4, K=3, P=2, 所有满足的序列有下面六种：

1. {1,1,2,3}   2) {1,2,1,3}
2. {1,2,2,3}   4) {1,2,3,1}
3. {1,2,3,2}   6) {1,2,3,3} 输入输出解释 3 4 3 2 2 3 1 3 4 16 3 30对第一组数据N=4, K=3, P=2, 所有满足的序列有下面六种：
4. {1,1,2,3}   2) {1,2,1,3}
5. {1,2,2,3}   4) {1,2,3,1}
6. {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

提示

没有写明提示

题目来源

没有写明来源