Eating Snacks

Time limit: 1.5 seconds

Memory limit: 512 megabytes

Problem Statement

As a foodie, Diana loves eating snacks. Diana plan to eat $a_i$ packs of snacks on $i$-th day within $n$ days, and if she plan to eat snacks on day $i$, she will definitely eat up all the $a_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 $m$ days strictly.

2.Within $m$ 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 $i$-th day within $m$ days, then Bella will allow her not to comply with the second rule on $(i+1)$-th day. Surely, Diana will definitely choose to eat $\textbf{strictly more}$ snacks on $(i+1)$-th day than on $i$-th day.

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

Now Diana wants to know how many ways to choose $m$ days from $n$ days to meet the above conditions.

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

Input

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

The second contains $n$ integers, the $i$-th number denoting $a_i(1 \leq a_i \leq 10^9)$.

Output

Print a single integer, denoting the answer to the question modulo $10^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 $m$.

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.