[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
University of Science and Technology of China
Online Judge for ACM/ICPC
Processed in 1.3ms with 1 query(s).