FINDMAX  Finding Maximum
One way of finding the maximum element in an array is to initialize a variable to the first element in the array, iterate through the remaining array, and update the variable whenever a value strictly greater than it is found. Assuming that the array contains N elements each in the range 1..K, how many such arrays exist such that the above algorithm performs exactly P updates? Initialization of the variable is not counted as an update.
For example,the possible arrays for N = 4, K = 3 and P = 2 are:
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}
Input
The first line contains T the number of test cases. There follow T lines, containing 3 space seperated integers N, K and P.
Output
Output T lines, one for each test case. On each line, output the answer as asked above. Since the answers can get very big, output the answer modulo 1000000007.
Example
Sample Input: 3 4 3 2 2 3 1 3 4 1 Sample Output: 6 3 30
Constraints
1 <= T <= 100
1 <= n <= 100
1 <= K <= 300
0 <= P < n
hide comments
arpit_01:
20180301 15:00:38
how to approach the recurrence relation?


nitesh kumar:
20140618 12:05:08
optimization tips here:


:D:
20110328 08:06:37
Not per test case, but per input :) 

Pratham Khandelwal:
20110128 12:25:30
Is O(n*K*P) per test case sufficient?

Added by:  Varun Jalan 
Date:  20100124 
Time limit:  0.131s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: NODEJS OBJC PERL6 SQLITE VB.NET 
Resource:  own problem used for Codechef Snackdown Onsite 