Dada una secuencia de $N$ $(1\le N\le 10,000)$ enteros $S_1$, ..., $S_N$ $(1\le Si<100,000)$, calcule el número de subsecuencias crecientes de $S$ con longitud $K$ $(1\le K\le 50yK\le N)$; es decir, el número de K-tuplas $i_1$, ..., $i_K$ tal que $1\le i_1<...<i_K\le$ $N$ and $S_{i1}$ < ... < $S_{iK}$.

Entrada

La primera línea contiene dos enteros $N$ y $K$. Las siguientes $N$ líneas contienen los enteros de la secuencia en orden.

Salida

Imprima un entero que representa el número de subsecuencias crecientes de $S$ con longitud $K$, módulo $5,000,000$.

Ejemplo de entrada

4 3
1
2
2
10

Ejemplo de salida

2