#P2022J. Eating Snacks

    ID: 111 Type: Default 1000ms 512MiB Tried: 51 Accepted: 4 Difficulty: 9 Uploaded By: Tags>福建师范大学第19届程序设计竞赛

Eating Snacks

Eating Snacks

Time limit: 1.5 seconds

Memory limit: 512 megabytes

Problem Statement

As a foodie, Diana loves eating snacks. Diana plan to eat aia_i packs of snacks on ii-th day within nn days, and if she plan to eat snacks on day ii, she will definitely eat up all the aia_i packs of snacks.

But strict team leader Bella will control the number of snacks Diana eats to prevent her from getting fat! Bella will control Diana eat snacks by some rules:

1.She can only eat snacks for mm days strictly.

2.Within mm days, the number of snacks eaten each day must be strictly less than the number of snacks eaten the previous day (excluding the first day).

3.Diana can start eating from any day.

But Bella is a good woman, so she relax the limit !

If Diana comply with the second rule on ii-th day within mm days, then Bella will allow her not to comply with the second rule on (i+1)(i+1)-th day. Surely, Diana will definitely choose to eat strictly more\textbf{strictly more} snacks on (i+1)(i+1)-th day than on ii-th day.

Especially\textbf{Especially}, on 11-st day Diana considered to have failed to comply with the second rule.

Now Diana wants to know how many ways to choose mm days from nn days to meet the above conditions.

Since the answer may be very large, you only need to print the result modulo 109+710^9 + 7.

Input

The first line contains two integers n,m(1n10000,1m100)n,m(1 \leq n \leq 10000, 1 \leq m \leq 100).

The second contains nn integers, the ii-th number denoting ai(1ai109)a_i(1 \leq a_i \leq 10^9).

Output

Print a single integer, denoting the answer to the question modulo 109+710^9 + 7.

5 5
2 1 3 1 2
1
5 5
1 2 1 3 1
0
5 1
2 1 3 1 2
5
7 3
2 1 3 1 2 3 2
11

Hints

On first sample and second sample has only one subsequence which length equals mm.

On first sample, Diana can start eating on first day, but the number of snacks eaten on the second day must be less than that on the first day, the number of snacks eaten on the third day must be more than on the second day...

On second sample, Diana start eating on first day, but the number of snacks eaten on the second day more than that on the first day. So the answer equals 0.