有 $n$ 个宽度为 1 的柱子从左到右紧密排列。从左往右第 $i$ 个柱子的高度为 $h_i$。

当下雨时，水会积聚在某些地方。当两个高柱子之间存在矮柱子时，就会发生这种情况。

形式化地讲，水会残留在任何既不属于柱子内部也不属于柱子边界的点上，且该点在同一高度上，其左侧和右侧都存在属于柱子的点。

我们关注积水的面积。如果高度 $h_i$ 均为整数，则该面积也是整数。老人的迷信预言，当积水面积能被 2 整除时，会带来幸福。

今天似乎要下雨了。然而，在此之前，你计划移除 $k$ 个柱子，即将它们的高度变为 0。在移除柱子的 $\binom{n}{k}$ 种可能性中，有多少种会导致积水面积为偶数？请输出结果对 $10^9 + 7$ 取模后的值。

输入格式

第一行包含两个整数 $n$ 和 $k$ ($1 \le n \le 25\,000, 0 \le k \le \min(25, n - 1)$)，表示柱子的数量和要移除的柱子数量。

第二行包含 $n$ 个整数 $h_1, \dots, h_n$ ($1 \le h_i \le 10^9$)，表示从左到右各柱子的高度。

输出格式

你需要输出一个数字，即移除 $k$ 个柱子使得积水面积为偶数的方案数，结果对 $10^9 + 7$ 取模。

样例

输入 1

7 1
2 5 2 4 1 6 2

输出 1

4

说明 1

左侧的大图描绘了柱子的初始设置。较小的图片描绘了移除一个柱子（箭头所指）的 7 种可能性。灰色区域描绘了积水。在 4 种情况下，积水面积（每张图片旁边的数字）是偶数。

输入 2

5 0
1 3 1 3 1

输出 2

1