K-инверсии

Пусть дана перестановка 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.

Примеры