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 ≤ n ≤ 60, 0 ≤ W ≤ 4 · 10¹⁸).

In the second line of input, there are n integers a_i: the masses of the weights. It is guaranteed that 1 ≤ a₁, 2 · a_i ≤ a_i+1, and a_n ≤ 10¹⁸.

Print a single line containing the answer to the problem.