길이가 K인 서로 다른 증가 부분 수열

길이가 $N$인 수열 $A_1, A_2, \dots, A_N$과 정수 $K$가 주어진다. $A$의 부분 수열 중에서 길이가 $K$이고 증가하는 것이 몇 개인지 구하라. 값의 나열이 같은 부분 수열은 고른 위치가 달라도 하나로 센다.

부분 수열은 $A$에서 원소를 0개 이상 지우고 남은 원소의 순서를 그대로 둔 수열이다. 길이가 $K$인 부분 수열 $B_1, B_2, \dots, B_K$가 증가한다는 것은 $1 \le i < K$인 모든 $i$에서 $B_i < B_{i+1}$이 성립한다는 뜻이다.

첫째 줄에 수열의 크기 $N$과 정수 $K$가 주어진다. ($1 \le N \le 100000$, $1 \le K \le 50$, $K \le N$)

둘째 줄에 $A_1, A_2, \dots, A_N$이 공백으로 구분되어 주어진다. ($1 \le A_i \le 100000$)

길이가 $K$이고 증가하는 서로 다른 부분 수열의 개수를 $5000000$으로 나눈 나머지를 한 줄에 출력한다.