B. K-inversions @ Dmitry Gozman Contest 1. Petrozavodsk training camp. Winter 2007 @ Timus Online Judge

B. K-inversions

Time limit: 1.0 second
Memory limit: 64 MB

Consider a permutation a₁, a₂, …, a_n (all a_i are different integers in range from 1 to n). Let us call k-inversion a sequence of numbers i₁, i₂, …, i_k such that 1 ≤ i₁ < i₂ < … < i_k ≤ n and a_i₁ > a_i₂ > … > a_{i_k}. Your task is to evaluate the number of different k-inversions 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 k-inversions in a given permutation. This number must be taken modulo 10⁹.

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