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