题目描述
有 $n$ 个宽度为 $1$ 的柱子从左到右排列，它们两侧相连。从左向右数第 $i$ 个柱子的高度为 $h_i$。
当下雨时，水可能会积聚在某些地方，比如两个高柱子之间有短柱子的情况下。
形式化的说，如果某个点不在柱子内部，点左侧和右侧均有格子高度不低于它，那么这个点就会积水。
例如下图展示了一个 $n = 10$，柱子高度分别为 $4, 2, 1, 8, 6, 2, 7, 1, 2, 3$ 的例子，积水的体积为 $2+3+1+5+2+1=14$。
有一天天降大雨，在雨后，坑洼的部分会产生积水。
你决定平整某些柱子，即，选出一些柱子使其高度变为 $0$，但是你只能平整恰好 $k$ 个柱子。
现在你想知道，在所有的 $\binom nk$ 种施工方案中，有多少种方案会使得最终的积水体积是偶数？答案对 $10^9+7$ 取模输出。
输入格式
第一行两个整数 $n,k$。
第二行 $n$ 个整数，表示 $h_i$。
输出格式
一个整数，表示答案对 $10^9+7$ 取模后的值。
样例输入 1
7 1 2 5 2 4 1 6 2
样例输出 1
4
样例输入/输出 2~9
见下发文件。
数据范围
对于所有数据，有：$1\le n\le 25000,1\le h_i\le 10^9,0\le k\le \min\{25,n-1\}$。
| 子任务编号 | 特殊性质 | 分值 |
|---|---|---|
| $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$ | 无 | $24$ |