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