Preparing NOJ

最大值

1000ms 65536K

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

Info

NOJ

Provider NOJ

Code NOJ1403

Tags

Submitted 0

Passed 0

AC Rate 0%

Date 04/20/2019 10:03:10

Related

Nothing Yet