
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 i^{th} kind of dishes has a mark number M_{i} ( 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 1^{st} dish to N^{th} dish). As soon as he finds the mark number of the i^{th}( i < N ) dish is larger than the i+1^{th} dish's, LCLL will eat the i^{th} 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. Input
The first line of each test case contains the numbers N, K ( 0 <= K < N <= 1000). The second line will cantain N integers, M_{1}, ..., M_{N}, respectively. ( 0 <= M_{1}, ..., M_{N} <= 2000000 ) The last test case is followed by two one zero. The input will contain no more than 100 test cases. Output For each test case output the answer MOD 1,000,000,007 on a single line. Sample Input 3 1 9 8 10 4 1 9 8 10 9 0 0 Sample Output 5 8 HINT 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 