题目描述

有 $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\}$。