Dada una secuencia de ~N~ ~(1 \leq N \leq 10,000)~ enteros ~S_1~, ..., ~S_N~ ~(1 \leq Si < 100,000)~, calcule el número de subsecuencias crecientes de ~S~ con longitud ~K~ \((1 \leq K \leq 50 \thinspace y \thinspace K \leq N)\); es decir, el número de K-tuplas ~i_1~, ..., ~i_K~ tal que ~1 \leq i_1 < ... < i_K \leq~ ~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