## FINDMAX - Finding Maximum

no tags

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 phantomhive: 2018-08-28 19:02:56 For this problem (p+1) <= k right? Last edit: 2018-08-28 19:03:11 hello_world123: 2018-06-21 09:50:05 For those scratching their head , just think about finding the number of arrays of length n , and given k and p, assuming you already know the number of arrays of length <= n for all possible values of k and p. arpit_01: 2018-03-01 15:00:38 how to approach the recurrence relation? nitesh kumar: 2014-06-18 12:05:08 optimization tips here: precalculate the values try avoid unnecessary iteration of loops [1..100][1..100][1..300] & use mod when needed & long long is sufficient.. :D: 2011-03-28 08:06:37 Not per test case, but per input :) Pratham Khandelwal: 2011-01-28 12:25:30 Is O(n*K*P) per test case sufficient? I am getting TLE