시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 512 MB 2 0 0 0.000%

문제

There are $n$ types of weights. The mass of one weight of type $i+1$ is not less than the mass of two weights of type $i$. You have exactly $2$ weights of each type.

Count the number of ways to select some weights with total mass equal to $W$. Two ways are different if for some $i$, the number of selected weights of type $i$ is different.

입력

In the first line of input, there are two integers $n$ and $W$: the number of types and the desired total mass ($1 \le n \le 60$, $0 \le W \le 4 \cdot 10^{18}$).

In the second line of input, there are $n$ integers $a_{i}$: the masses of the weights. It is guaranteed that $1 \le a_{1}$, $2 \cdot a_{i} \le a_{i+1}$, and $a_{n} \le 10^{18}$.

출력

Print a single line containing the answer to the problem.

예제 입력 1

5 100
2 5 10 21 49

예제 출력 1

3