El Dorado

Interview

Time limit1sMemory limit128 MB

Summary

Count the increasing subsequences of length exactly k in a sequence of n distinct numbers, for several test cases.

Level: Medium5 of 10
Topics: Dynamic programming, Array, Combinatorics
Solved: No attempts yet

Problem

A casino game shows a sequence of $n$ numbers on its screen, and the player must guess how many increasing subsequences of length $k$ the sequence contains.

A subsequence of a sequence $a_1, a_2, \ldots, a_n$ is any $a_{i_1}, a_{i_2}, \ldots, a_{i_l}$ chosen by indices $1 \le i_1 < i_2 < \cdots < i_l \le n$ . Such a subsequence is increasing if $a_{i_{j-1}} < a_{i_j}$ holds for every $1 < j \le l$ .

Given the sequence shown on the screen, write a program that counts the number of increasing subsequences of length $k$ .

Input

The input consists of several test cases. The first line of each test case contains two integers $n$ and $k$ ( $1 \le k \le n \le 100$ ). The second line contains the sequence $a_1, \ldots, a_n$ , whose elements are pairwise distinct ( $-10000 \le a_i \le 10000$ ).

The last line of the input contains two zeros and must not be processed.

Output

For each test case, print the number of increasing subsequences of length $k$ , one per line. This value fits within the range of a 64-bit integer.

Examples3

Example 1

Input

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

Expected output

252
0

Example 2
Input
```
5 1
5 3 1 2 4
0 0
```
Expected output
```
5
```
Example 3
Input
```
6 6
1 2 3 4 5 6
0 0
```
Expected output
```
1
```