Increasing subsequences of length K

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.

A subsequence is $A_{i_1}, A_{i_2}, \dots, A_{i_K}$ for indices $i_1 < i_2 < \dots < i_K$. It is increasing when $A_{i_1} < A_{i_2} < \dots < A_{i_K}$ holds, so two equal values can never sit next to each other in it. Two subsequences that use different index sets are counted separately even when their values are identical.

The first line contains the length of the sequence $N$ ($1 \le N \le 100000$) and an integer $K$ ($1 \le K \le 50$, $K \le N$), separated by a space.

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

Print the number of increasing subsequences of length $K$, modulo 5,000,000, on the first line.