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_i1 > a_i2 > … > a_ik. Your task is to evaluate the number of different k-inversions in a given permutation.

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 the number of different k-inversions in a given permutation. This number must be taken modulo 10⁹.