ELDORADO  El Dorado
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 a_{1}, ..., a_{n} is defined as a_{i1}, ..., a_{il}, where 1 ≤ i_{1} < i_{2} < ... < i_{l} ≤ n. The subsequence is increasing, if a_{ij1} < a_{ij} 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 a_{i} (10000 ≤ a_{i} ≤ 10000 ), where a_{i} is the i^{th} 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:
20161229 20:55:23
Try INQSEQ after this problem. There's some funny business with BIT there.


gautams:
20150821 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:  20080712 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  University of Ulm Local Contest 2008 