ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

## 1523. K-inversions

Time limit: 1.0 second
Memory limit: 64 MB
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 integers n and k (1 ≤ n ≤ 20000; 2 ≤ k ≤ 10). The second line is filled with n integers ai.

### Output

Output the number of different k-inversions in a given permutation. This number must be taken modulo 109.

### Samples

inputoutput
```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