% Source: PTZ Winter07\20070129

\begin{problem}{$K$-инверсии}{kinverse.in}{kinverse.out}{2 секунды}{64 мегабайта}

Пусть дана перестановка $a_1, a_2, \ldots, a_n$. Назовем $k$-инверсией набор 
чисел $i_1, i_2, \ldots, i_k$ таких, что $1\le i_1<i_2<\ldots<i_k \le n$ и 
$a_{i_1}>a_{i_2}>\ldots>a_{i_k}$. Ваша задача~--- подсчитать 
количество различных $k$-инверсий в заданной перестановке.
                                                                    
\InputFile

В первой строке входного файла находятся число $n$~--- длина перестановки 
($1 \le n \le 20\,000$), и число $k$ ($2 \le k \le 10$). Во второй строке $n$ 
чисел~--- сама перестановка.

\OutputFile

В выходной файл выведите единственное число~--- количество $k$-инверсий 
в заданной перестановке по модулю $10^9$.

\Example

\begin{example}
\exmp{
3 2
3 1 2
}{
2
}%
\exmp{
5 3
5 4 3 2 1
}{
10
}%
\end{example}

\end{problem}
