当前没有测试数据。

题目描述

小A是一位量子计算研究员，他正在配置一个由 n 个量子比特组成的序列。 每个量子比特编号从 1 到 n，第 i 个量子比特的能量值必须是 [0, a_i] 之间的整数（含 0 和 a_i 两个值）。 他需要为每个量子比特配置一个能量值，从而实现量子纠缠的目标。要实现量子纠缠，每个量子比特的能量值需要满足特殊性质要求：

1. 每个量子比特的能量值都必须是非负的整数。
2. 任意相邻的两个量子比特的能量值必须一奇一偶。
3. 整个序列的所有量子比特的能量值之和不超过 m。 请问会有多少种量子比特能量值的配置方案，能够实现量子纠缠的目标？

输入格式

第一行两个整数 n, m。 接下来一行 n 个整数，即 a_1~a_n。

输出格式

一行一个整数，表示方案数。

样例输入 1

3 6
6 6 6

样例输出 1

20

样例输入 2

3 6
3 3 3

样例输出 2

14

样例输入 3

6 30
8 7 6 8 5 7

样例输出 3

6439

样例说明

样例 1 有以下 20 种方案：

0,1,0、2,1,0、4,1,0、0,3,0、2,3,0、0,5,0、1,0,1、3,0,1、5,0,1、1,2,1、3,2,1、1,4,1、0,1,2、2,1,2、0,3,2、1,0,3、3,0,3、1,2,3、0,1,4、1,0,5

样例 2 有以下 14 种方案：

0,1,0、2,1,0、0,3,0、2,3,0、1,0,1、3,0,1、1,2,1、3,2,1、0,1,2、2,1,2、0,3,2、1,0,3、3,0,3、1,2,3

数据范围与约定

• 对于 100% 的数据，1≤n≤6，0≤m≤100，0≤a_i≤8。
• 存在 30% 的数据：保证 n=2。
• 存在 30% 的数据：保证 a_i=1。
• 存在 40% 的数据：没有特殊限制。