Пусть дана перестановка a[1]
, a[2]
, ..., a[n]
. Назовем k-инверсией такой набор чисел i[1]
, i[2]
, ..., i[k]
, что
1 ≤ i[1]
< i[2]
< ... < i[k]
≤ n
и
a[i1]
> a[i2]
> ... > a[ik]
.
Ваша задача - подсчитать количество различных k-инверсий в заданной перестановке.
В первой строке находятся длина перестановки n (1 ≤ n ≤ 20000) и число k (2 ≤ k ≤ 10). Во второй строке n чисел - сама перестановка.
Выведите единственное число - количество k-инверсий в заданной перестановке по модулю 10^9
.