2008/2009 ACM International Collegiate Programming Contest

University of Ulm Local Contest

# Problem E: El Dorado

Source file: eldorado.(c|cc|hs|java|pas)

Input file: eldorado.in

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*_{ij-1} < 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 Specification

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 Specification

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").

#### Sample Input

10 5
1 2 3 4 5 6 7 8 9 10
3 2
3 2 1
0 0

#### Sample Output

252
0