题目描述

构造长度为 $n$ 的非负整数序列，第 $i$ 个数可以取 $0$ 至 $a_i$。要求任意两个相邻数的奇偶性不同，并且所有数的和不超过 $m$。请求出满足条件的序列数量。

输入格式

第一行包含两个整数 $n,m$。 第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

输出一个整数，表示满足条件的序列数量。

样例

3 6
6 6 6

20

数据范围与提示

• $1 \le n \le 6$
• $0 \le m \le 100$
• $0 \le a_i \le 8$