Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

AL_29_08 - Rozmowa kwalifikacyjna

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ć 232 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 <= 106 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 109.

Przykład

Wejście:
4 3
4 2 3 1

Wyjście: 2

Dodane przez:Adam Bąk
Data dodania:2016-08-25
Limit czasu wykonania programu:1s-4.5s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM64 GOSU

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.