Distinct Increasing Subsequences of Length K

Time limit2sMemory limit512 MB

Summary

Count the distinct value sequences of length K that appear as increasing subsequences of the given array, modulo 5000000.

Level: Medium7 of 10
Topics: Dynamic programming, Sorting, Combinatorics
Solved: No attempts yet

Problem

You are given a sequence $A_1, A_2, \dots, A_N$ of length $N$ and an integer $K$ . Count the subsequences of $A$ that have length $K$ and are increasing. Two subsequences with the same sequence of values count as one, even when they are taken from different positions.

A subsequence is what remains after deleting zero or more elements of $A$ and keeping the order of the rest. A subsequence $B_1, B_2, \dots, B_K$ of length $K$ is increasing when $B_i < B_{i+1}$ holds for every $i$ with $1 \le i < K$ .

Input

The first line contains the size $N$ of the sequence and the integer $K$ . ( $1 \le N \le 100000$ , $1 \le K \le 50$ , $K \le N$ )

The second line contains $A_1, A_2, \dots, A_N$ , separated by spaces. ( $1 \le A_i \le 100000$ )

Output

Print, on one line, the number of distinct increasing subsequences of length $K$ modulo $5000000$ .

Examples2

Example 1
Input
```
4 3
1 2 2 10
```
Expected output
```
1
```
Example 2
Input
```
5 1
3 3 1 2 2
```
Expected output
```
3
```