题目内容

小明有一个包含 $n$ 个整数的序列 $a_1, a_2, \dots, a_n$。他可以执行一次操作：选择一个位置 $i$，将该位置的值变为它的相反数，即 $a_i \gets -a_i$。操作后，如果序列所有元素之和落在 $[0, M]$ 这个区间内，则这次操作被称为有效的。小明想知道有多少种不同的选择（即选择不同位置进行操作）是有效的。注意：即使操作后总和相同，只要选择的位置不同，就算不同的有效操作。

序列的长度 $n$ 满足 $1 \le n \le 2 \times 10^5$，上界 $M$ 满足 $1 \le M \le 4 \times 10^{18}$，序列中的每个元素的绝对值均不超过 $2 \times 10^9$。

输入描述

第一行包含两个整数 $n$ 和 $M$，分别表示序列长度和总和上界。 第二行包含 $n$ 个整数，表示序列的初始元素，以空格分隔。

输出描述