Informatyka MIMUW

To laboratorium jest przede wszystkim poświęcone wprowadzeniu bardzo użytecznej w praktyce struktury danych, jaką jest drzewo przedziałowe.

Zadanie KIN ( $\displaystyle k$-inwersje)

Dostępna pamięć: 64MB.

Niech $\displaystyle a_1,\ldots,a_n$ będzie permutacją liczb od 1 do $\displaystyle n$. $\displaystyle k$-inwersją w tej permutacji nazywamy ciąg indeksów $\displaystyle i_1,i_2,\ldots,i_k$, taki że $\displaystyle 1 \le i_1 < i_2 < \ldots < i_k \le n$ oraz $\displaystyle a_{i_1} > a_{i_2} > \ldots > a_{i_k}$. Twoim zadaniem jest wyznaczenie liczby $\displaystyle k$-inwersji w zadanej permutacji.

Wejście
Pierwszy wiersz wejścia zawiera dwie liczby całkowite $\displaystyle n$ oraz $\displaystyle k$ ( $\displaystyle 1 \le n \le 20\,000$, $\displaystyle 2 \le k \le 10$ ). Drugi wiersz zawiera permutację liczb $\displaystyle \{1,\ldots,n\}$.

Wyjście
Twój program powinien wypisać resztę z dzielenia przez $\displaystyle 10^9$ z liczby $\displaystyle k$-inwersji w podanej permutacji.

Przykład

Dla danych wejściowych:
4 3
4 3 1 2
poprawnym wynikiem jest:
2