题目描述

小 A 是一位量子计算研究员，他正在配置一个由 $n$ 个量子比特组成的序列。

每个量子比特编号从 $1$ 到 $n$，第 $i$ 个量子比特的能量值必须是 $[0, a_i]$ 之间的整数（含 $0$ 和 $a_i$ 两个值）。

他需要为每个量子比特配置一个能量值，从而实现量子纠缠的目标。要实现量子纠缠，每个量子比特的能量值，需要满足特殊性质要求：

• 每个量子比特的能量值都必须是非负的整数。
• 任意相邻的两个量子比特的能量值必须一奇一偶。
• 整个序列的所有量子比特的能量值之和不超过 $m$。

请问会有多少种量子比特能量值的配置方案，能够实现量子纠缠的目标？

输入格式

第一行两个整数 $n, m$。

接下来一行 $n$ 个整数，即 $a_1 \sim a_n$。

输出格式

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

样例 #1

输入

3 6
6 6 6

输出

20

样例 #2

输入

3 6
3 3 3

输出

14

样例 #3

输入

6 30
8 7 6 8 5 7

输出

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 \le n \le 6$，$0 \le m \le 100$，$0 \le a_i \le 8$。

存在 $30\%$ 的数据：保证 $n = 2$。

存在 $30\%$ 的数据：保证 $a_i = 1$。

存在 $40\%$ 的数据：没有特殊限制。