ZOJ Problem Set - 3253
Watashi is going to hold a party at his villa 218, he wishes to invite all his friends. He has prepared N kinds of dishes, moreover, the ith kind of dishes has a mark number Mi ( i = 1, 2, ..., N ) (the dishes with the SAME mark number are EQUIVALENT). Before the party, Watashi will put all of his N delicate dishes in one line.
One of Watashi's friends, LCLL, always arrived at the party first, and ate nearly all the dishes up. But LCLL has a strange habit, he will choose dishes from left to right(from 1st dish to Nth dish). As soon as he finds the mark number of the ith( i < N ) dish is larger than the i+1th dish's, LCLL will eat the ith dish up, or he will go toward the next dish and never go backward.
Watashi tries his best to avoid LCLL from eating more than K dishes up, he wants to know that how many permutations of N dishes will achieve his goal.
Please help the poor host to calculate it.
The first line of each test case contains the numbers N, K ( 0 <= K < N <= 1000).
The second line will cantain N integers, M1, ..., MN, respectively. ( 0 <= M1, ..., MN <= 2000000 )
The last test case is followed by two one zero.
The input will contain no more than 100 test cases.
For each test case output the answer MOD 1,000,000,007 on a single line.
3 1 9 8 10 4 1 9 8 10 9 0 0
If the permutation is "9, 10, 8", LCLL will eat one dish (10).
If Watashi has 2 kinds of dishes and the mark numbers are the same, there's just one way to permutate the dishes.
Author: OUYANG, Jialin
Source: ZOJ Monthly, September 2009