Subsecuencias crecientes


Submit solution

Points: 100 (partial)
Time limit: 10.0s
Memory limit: 64M

Authors:
Problem type
Allowed languages
Ada, BrainF***, C#, C++, Dart, Go, Java, JS, Kotlin, Lua, Pascal, Prolog, Python, Swift, VB

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

Comments

There are no comments at the moment.