ELDORADO - El Dorado

no tags 

Bruce Force has gone to Las Vegas, the El Dorado for gamblers. He is interested especially in one betting game, where a machine forms a sequence of n numbers by drawing random numbers. Each player should estimate beforehand, how many increasing subsequences of length k will exist in the sequence of numbers.

A subsequence of a sequence a1, ..., an is defined as ai1, ..., ail, where 1 ≤ i1 < i2 < ... < il ≤ n. The subsequence is increasing, if aij-1 < aij for all 1 < j ≤ l.

Bruce doesn't trust the Casino to count the number of increasing subsequences of length k correctly. He has asked you if you can solve this problem for him.

Input

The input contains several test cases. The first line of each test case contains two numbers n and k (1 ≤ k ≤ n ≤ 100), where n is the length of the sequence drawn by the machine, and k is the desired length of the increasing subsequences. The following line contains n pairwise distinct integers ai (-10000 ≤ ai ≤ 10000 ), where ai is the ith number in the sequence drawn by the machine.

The last test case is followed by a line containing two zeros.

Output

For each test case, print one line with the number of increasing subsequences of length k that the input sequence contains. You may assume that the inputs are chosen in such a way that this number fits into a 64 bit signed integer (in C/C++, you may use the data type "long long", in Java the data type "long").

Example

Input:
10 5
1 2 3 4 5 6 7 8 9 10
3 2
3 2 1
0 0
Output:
252
0

hide comments
siddharth9820: 2016-12-29 20:55:23

Try INQSEQ after this problem. There's some funny business with BIT there.

gautams: 2015-08-21 21:12:01

Can someone please give me good input test cases to test my code?? It works properly for the test cases above, but gives a wrong answer when I submit the solution.


Added by:Adrian Kuegel
Date:2008-07-12
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:University of Ulm Local Contest 2008