AlgoLiga 2018

Bitomir właśnie skończył studia i szuka pracy. Marzy oczywiście o posadzie programisty w firmie Gooli. Niestety poległ tam na rozmowie kwalifikacyjnej i musi czekać 2³² miesięcy na kolejną. Zadanie które otrzymał brzmiało:

Dana jest permutacja liczb od 1 do n oraz liczba naturalna k. Znajdź liczbę malejących podciągów tej permutacji, których długość wynosi k.

Był pewien, że już kiedyś rozwiązywał podobne zadanie i zamiast skupić się na tym, starał się przypomnieć rozwiązanie tamtego. Czy według Ciebie była to prosta rozmowa?

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby naturalne 1 <= n <= 10⁶ oraz 2 <= k <= 10. Drugi wiersz zawiera permutację liczb naturalnych od 1 do n.

Wyjście

Na wyjście należy wypisać szukaną liczbę modulo 10⁹.

Przykład

Wejście:
4 3
4 2 3 1

Wyjście:
2