There are $n$ pillars of width $1$ arranged from left to right, connected side by side. The height of the $i$-th pillar from the left is $h_i$.
When it rains, water may accumulate in certain areas, such as when there are shorter pillars between two taller pillars.
Formally, if a point is not inside a pillar, and there are grid cells with heights no less than the point's height both to its left and to its right, then this point will accumulate water.
For example, the figure below shows an example with $n = 10$ and pillar heights $4, 2, 1, 8, 6, 2, 7, 1, 2, 3$, where the volume of accumulated water is $2+3+1+5+2+1=14$.
One day, heavy rain falls, and after the rain, water accumulates in the depressions.
You decide to level some pillars, meaning you choose some pillars and set their heights to $0$. However, you can only level exactly $k$ pillars.
Now you want to know, among all $\binom nk$ possible construction plans, how many result in an even volume of accumulated water? Output the answer modulo $10^9+7$.
Input
The first line contains two integers $n$ and $k$.
The second line contains $n$ integers, representing $h_i$.
Output
An integer representing the answer modulo $10^9+7$.
Examples
Input 1
7 1 2 5 2 4 1 6 2
Output 1
4
Input 2~9
See the provided files.
Constraints
For all data, $1\le n\le 25000, 1\le h_i\le 10^9, 0\le k\le \min\{25, n-1\}$.
| Subtask ID | Special Property | Score |
|---|---|---|
| $1$ | $n \le 15, h_i \le 10$ | $10$ |
| $2$ | $n \le 40$ | $12$ |
| $3$ | $n \le 400, k\le 8$ | $8$ |
| $4$ | $n \le 400$ | $6$ |
| $5$ | $n \le 3000, k \le 8$ | $8$ |
| $6$ | $k \le 8$ | $10$ |
| $7$ | $n \le 3000$ | $12$ |
| $8$ | $h_i \le h_{i+1}$ | $10$ |
| $9$ | None | $24$ |