题目描述

有 $N$ 个糖果碗排成一行，编号为 $0,1,\ldots,N-1$。第 $i$ 个碗初始有 $C_i$ 颗糖果。

两名玩家轮流操作，无法进行合法操作的玩家输。每次操作可以选择以下两种方式之一：

1. 选择一个至少有两颗糖果的碗，吃掉其中恰好两颗糖果。
2. 选择一个正奇数 $k$，再选择一个编号 $x\ge k$ 且至少有 $k$ 颗糖果的碗。把碗 $x$ 中恰好 $k$ 颗糖果移动到碗 $x-k$ 中。

在游戏开始前，还必须把额外的 $E$ 颗糖果全部放入这些碗中。每颗额外糖果可以放入任意一个碗。糖果不可区分，因此不同的最终分配方案仅由最终的 $N$ 元组决定。

如果在某个最终分配下，先手玩家存在必胜策略，则称该分配为必胜分配。

请计算所有可能的额外糖果分配方案中，必胜分配的数量，并对 $10^9+7$ 取模。

输入格式

第一行包含两个整数：

N E

其中：

• $1\le N\le100$；
• $0\le E\le10^6$。

第二行包含 $N$ 个整数 $C_0,C_1,\ldots,C_{N-1}$，满足 $0\le C_i\le10^9$。

输出格式

输出一个整数，表示必胜分配数量对 $10^9+7$ 取模后的结果。

样例 1

输入

1 3
4

输出

1

样例 2

输入

7 0
0 0 0 0 0 0 1

输出

0

样例 3

输入

7 0
0 0 0 0 0 5 0

输出

1

样例 4

输入

3 2
1 0 0

输出

4

样例 5

输入

3 0
0 0 0

输出

0

样例 6

输入

3 4
1 2 3

输出

9