| [Home|Training|Problems|Contests|C Language] | [Login|Register] |
|
Problems Status Rank |
Problem 1267
Max
Time Limit: 1000ms
Memory Limit: 65536kb Description
If your task is to find the maximum number in an array a [], you will always consider it as a piece of cake. The poor code can be written as follows:Void Find-Max () { Max=a[0]; For(i=1; i<N; i++) If (a[i]>Max) Max=a[i]; } If a[i]>Max (0<i<N), Max will be updated once. Here comes another problem: if the element of an array will always be between 1 and K, then how many legal arrays can be found with updating Max exactly P times by means of above algorithm? For example, assuming N=4, K=3, P=2.then the legal arrays are as follows: {1, 1, 2, 3} {1, 2, 1, 3} {1, 2, 3, 3} {1, 2, 3, 2} {1, 2, 3, 1} {1, 2, 2, 3} And there exists 6 legal arrays. Input
A number T in the first line, indicating the case number (T<=100).Each case contains three numbers: N, K, and P. (1<=N<=100, 1<=K<=300, 0<=P<N). Output
For each case, output the result mod 1000000007.
Sample Input
1 4 3 2 Sample Output
6 |