K-inversions

Consider a permutation a[1], a[2], ..., a[n] (all a[i] are different integers in range from 1 to n). Let us call k-inversion a sequence of numbers i[1], i[2], ..., i[k] such that

1 ≤ i[1] < i[2] < ... < 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.

Input

The first line 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 k-inversions in a given permutation. The number must be taken modulo 10^9.

Examples