길이가 K인 증가하는 부분 수열

길이가 $N$인 수열 $A_1, A_2, \dots, A_N$과 정수 $K$가 주어진다. 수열 $A$의 부분 수열 중에서 길이가 $K$이면서 증가하는 것이 몇 개인지 구하시오.

부분 수열은 인덱스 $i_1 < i_2 < \dots < i_K$를 골라 만든 $A_{i_1}, A_{i_2}, \dots, A_{i_K}$이다. 증가한다는 것은 $A_{i_1} < A_{i_2} < \dots < A_{i_K}$가 성립한다는 뜻이므로, 값이 같은 원소가 이웃해 들어갈 수는 없다. 값이 같더라도 고른 인덱스가 하나라도 다르면 서로 다른 부분 수열로 센다.

첫째 줄에 수열의 길이 $N$ ($1 \le N \le 100000$)과 정수 $K$ ($1 \le K \le 50$, $K \le N$)가 공백을 사이에 두고 주어진다.

둘째 줄에 $A_1, A_2, \dots, A_N$이 공백을 사이에 두고 주어진다. ($1 \le A_i \le 100000$)

길이가 $K$이면서 증가하는 부분 수열의 개수를 5,000,000으로 나눈 나머지를 첫째 줄에 출력한다.