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 contains integers n and k
(1 ≤ n ≤ 20000; 2 ≤ k ≤ 10).
The second line is filled with n integers a_{i}.
Output
Output the number of different kinversions in a given permutation. This 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