Consider a permutation a_{1}, a_{2}, …, a_{n} (all
a_{i} are different integers in range from 1 to n). Let us call kinversion
a sequence of numbers i_{1}, i_{2}, …, i_{k} such that
1 ≤ i_{1} < i_{2} < … < i_{k} ≤ n
and a_{i}_{1} > a_{i}_{2} > … > a_{ik}. Your task is to evaluate
the number of different kinversions in a given permutation.
Input
The first line of the input contains two integers n and k
(1 ≤ n ≤ 20000, 2 ≤ k ≤ 10).
The second line is filled with n numbers a_{i}.
Output
Output a single number — the number of kinversions in a given permutation.
The number must be taken modulo 10^{9}.
Samples
input  output 

3 2
3 1 2
 2 
5 3
5 4 3 2 1
 10

Problem Author: Dmitry Gozman
Problem Source: Dmitry Gozman Contest 1, Petrozavodsk training camp, January 2007