题目整理

Description

给定数列A[1..N]，寻找最大值的方法为：枚举A[2]到A[N]，当A[i]大于A[1]时，将A[1]更新为A[i]。假设所有数都在范围[1, K]内，有多少长度为N的数列满足A[1]被更新的次数恰好为P？

Input Format

• 多组数据
• 第一行：一个数T为数据组数
• 接下来T行：三个数N、K和P

Output Format

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

输入

3
4 3 2
2 3 1
3 4 1

输出

6
3
30

解释

• 第一组数据：N=4, K=3, P=2，满足的序列有6种：{1,1,2,3}、{1,2,1,3}、{1,2,2,3}、{1,2,3,1}、{1,2,3,2}、{1,2,3,3}

数据范围

• 前20%的数据：T ≤ 5
• 前50%的数据：1 ≤ N ≤ 50，1 ≤ K ≤ 100
• 完整数据：T ≤ 1000，1 ≤ N ≤ 150，0 ≤ P < N，1 ≤ K ≤ 300