% Source: PTZ Winter07\20070129

\begin{problem}{$K$-inversions}{kinverse.in}{kinverse.out}{2 seconds}{64 megabytes}

Consider a permutation $a_1, a_2, \ldots, a_n$ (all
$a_i$ are different integers in range from 1 to $n$). Let us call \textit{$k$-inversion}
a sequence of numbers $i_1, i_2, \ldots, i_k$ such that $1\le i_1<i_2<\ldots<i_k \le n$
and $a_{i_1}>a_{i_2}>\ldots>a_{i_k}$. Your task is to evaluate
the number of different $k$-inversions in a given permutation.
                                                                    
\InputFile

The first line of the input contains two integers $n$ and $k$
($1 \le n \le 20 \, 000$, $2 \le k \le 10$).
The second line is filled with $n$ numbers $a_i$.

\OutputFile

Output a single number --- the number of $k$-inversions in a given permutation.
The number must be taken modulo $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}
