짝수 빗물

너비가 $1$인 기둥 $n$개가 옆면끼리 맞닿은 채 왼쪽에서 오른쪽으로 놓여 있다. 왼쪽에서 $i$번째 기둥의 높이는 $h_i$이다.

비가 내리면 일부 자리에 물이 고일 수 있다. 짧은 기둥이 두 높은 기둥 사이에 있을 때 그렇다.

정확히는, 기둥의 내부나 경계에 속하지 않는 점 가운데, 같은 높이에서 왼쪽의 어떤 기둥과 오른쪽의 어떤 기둥에 동시에 걸쳐 있는 점에는 물이 남는다.

고인 물의 넓이가 관심사다. 모든 $h_i$가 정수이면 이 넓이도 정수이다. 노인들의 미신에 따르면 고인 물의 넓이가 $2$로 나누어떨어질 때 행복이 찾아온다.

오늘 비가 올 예정이다. 그 전에 $k$개의 기둥을 제거할 계획이다. 제거한다는 것은 해당 기둥의 높이를 $0$으로 바꾸는 것이다. $\binom{n}{k}$가지 제거 방법 중 고인 물의 넓이가 짝수가 되는 경우는 몇 가지인가? 답은 $10^9+7$로 나눈 나머지로 출력한다.

첫 줄에 두 정수 $n$과 $k$가 주어진다 ($1 \leq n \leq 25\,000$, $0 \leq k \leq \min(25, n - 1)$). 둘째 줄에는 $n$개의 정수 $h_1, \ldots, h_n$이 주어진다 ($1 \leq h_i \leq 10^9$).

고인 물의 넓이가 짝수가 되도록 $k$개의 기둥을 제거하는 방법의 수를 $10^9+7$로 나눈 나머지로 한 줄에 출력한다.

첫 번째 샘플 설명이다. 왼쪽의 큰 그림은 초기 상태이다. 작은 그림들은 기둥 하나를 제거하는 7가지 경우를 각각 보여 준다(화살표가 제거할 기둥을 가리킨다). 회색 영역이 고인 물이다. 4가지 경우에서 고인 물의 넓이(각 그림 옆 숫자)가 짝수이다.