Задачи
K-инверсии
K-инверсии
Пусть дана перестановка a1
, a2
, ..., an
. Назовем k-инверсией такой набор чисел i1
, i2
, ..., ik
, что
1 ≤ i1
< i2
< ... < ik
≤ n
и
ai1
> ai2
> ... > aik
.
Ваша задача - подсчитать количество различных k-инверсий в заданной перестановке.
Входные данные
В первой строке находятся длина перестановки n (1 ≤ n ≤ 20000) и число k (2 ≤ k ≤ 10). Во второй строке n чисел - сама перестановка.
Выходные данные
Выведите единственное число - количество k-инверсий в заданной перестановке по модулю 109
.
Входные данные #1
3 2 3 1 2
Выходные данные #1
2