说明

龙岩位于福建的西部，属于山区，矿产资源丰富，自然条件好，有许多闻名于世的特产，其中“龙岩花生”名气颇大。

ZYR 在散步的时候遇到了一个卖龙岩花生的老人。正好 ZYR 想吃花生，于是他开始买花生。

老人的花生十分神奇，有单颗单粒的、单颗双粒的、……、单颗 $n$ 粒的。其中单颗 $i$ 粒的共有 $a_i$ 颗。

ZYR 可以选择 $k$ 颗花生。因为 ZYR 有强迫症，所以他希望他买的花生的粒数的总和为奇数。问他有多少种购买方案。由于答案可能是巨大的，所以请将答案对 $10^9+7$ 取模。

注意，选择花生需考虑顺序（如果你不知道什么是考虑顺序，请看样例解释）！

输入格式

第一行两个正整数 $n,k$。

第二行 $n$ 个非负整数，表示 $a_1,a_2,\ldots,a_n$。

输出格式

一行一个正整数，表示购买方案。

样例

2 2
3 2

6

样例

5 2
1 3 5 7 9

150

提示

样例 #1 解释：

我们把三个单颗单粒的花生编号为 $1,2,3$，两个单颗双粒的花生编号为 $4,5$；

那么有如下方案：

• 选择 $1,4$；

• 选择 $1,5$；

• 选择 $2,4$；

• 选择 $2,5$；

• 选择 $3,4$；

• 选择 $3,5$；

共有 $6$ 种方案。

对于 $100\%$ 的数据，$1\le n\le 2\times 10^3,0\le a_i\le 2\times 10^3,1\le k\le\sum a_i\le 4\times 10^6$。