#33 「 立方体 」

统计

在n维空间中,一个单位立方体由$2^n$个点组成。

他们的坐标形如$(x_1,x_2,\ldots,x_n)$,$x_i \in \{0,1\}$。

定义n维空间中两点的距离为其曼哈顿距离,点p $(p_1,p_2,\ldots,p_n)$ 与点q $(q_1,q_2,\ldots,q_n)$的距离为$\sum_{i=1}^n{|p_i - q_i|}$。

现在给你单位立方体上一点p以及一个整数k,问你与点p距离为k的单位立方体上点的数量。

因为这样的点可能很多,所以请对$10^9+7$取模。

输入格式

输入共两行。

第一行两个数字,表示n和k。

第二行n个数字,表示p的坐标。

输出格式

一行一个数字,表示点的数量。

样例数据

input

3 2
1 1 0

output

3

样例解释

距离(1,1,0)为2的点共三个(0,0,0), (0,1,1), (1,0,1)。

数据规模与约定

$1 \le k \le n \le 10^6$。

时间限制:1s

空间限制:512MB

Author: zrt