[AdditionalFile5519.zip](file://AdditionalFile5519.zip?type=additional_file)

#5519. 「PA 2019 Final」Parzysty deszcz

标签: 传统 | 时间限制: 9000 ms | 内存限制: 512 MiB |

题目描述

题目译自 PA 2019 Final Parzysty deszcz

有 $n$ 根柱子排成一排，每根柱子宽度为 $1$。柱子侧面相邻，第 $i$ 根柱子的高度为 $h_{i}$。当下雨时，某些地方可能会积水。这发生在两根高柱子之间有低柱子时——此时水无法流走。

形式上，水会留在每个不是柱子内部或边缘的点上，但在这个高度上，左侧某处和右侧某处存在柱子。

水的体积定义为积水区域的面积。如果柱子高度 $h_{i}$ 为整数，则该体积为非负整数。一个古老的迷信认为，水的体积为偶数会带来好运。

雨即将来临，但你计划先移除 $k$ 根柱子，即将其高度改为 $0$。在所有 $\binom{n}{k}$ 种选择移除柱子的方案中，有多少种方案会导致雨后水的体积为偶数？请输出结果对 $10^{9}+7$ 取模的值。

输入格式

输入数据的第一行包含两个整数 $n$ 和 $k$ $(1 \leq n \leq 25000, 0 \leq k \leq \min(25, n-1))$，分别表示柱子数量和要移除的柱子数量。

第二行包含 $n$ 个整数 $h_{1}, h_{2}, \ldots, h_{n}$ $(1 \leq h_{i} \leq 10^{9})$，表示从左到右各柱子的高度。

输出格式

输出应包含一个整数，表示移除 $k$ 根柱子后，雨后水体积为偶数的方案数量对 $10^{9}+7$ 取模的结果。

样例 1

输入

7 1
2 5 2 4 1 6 2

输出

4

第一个样例中，左侧大图展示了柱子的初始排列。右侧小图展示了移除一根柱子（由箭头指示）的 $7$ 种可能性。灰色区域表示雨后的积水。在 $4$ 种情况下，水的体积（每幅图旁标注的数字）为偶数。

样例 2

输入

5 0
1 3 1 3 1

输出

1