Consider a permutation a1, a2, ..., an (all ai are different integers in range from 1 to n). Let us call k-inversion a sequence of numbers i1, i2, ..., ik such that

1 ≤ i1 < i2 < ... < ik ≤ n

and

ai1 > ai2 > ... > aik.

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 ai.

Output

Output a single number — the number of k-inversions in a given permutation. The number must be taken modulo 109.