#P17359. PM18239_CandyBowlGame

PM18239_CandyBowlGame

题目描述

有 NN 个糖果碗排成一行,编号为 0,1,…,N−10,1,\ldots,N-1。第 ii 个碗初始有 CiC_i 颗糖果。

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

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

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

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

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

输入格式

第一行包含两个整数:

N E

其中:

  • 1≤N≤1001\le N\le100;
  • 0≤E≤1060\le E\le10^6。

第二行包含 NN 个整数 C0,C1,…,CN−1C_0,C_1,\ldots,C_{N-1},满足 0≤Ci≤1090\le C_i\le10^9。

输出格式

输出一个整数,表示必胜分配数量对 109+710^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