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.
Input
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 · 1018).
In the second line of input, there are n integers ai: the masses of the weights. It is guaranteed that 1 ≤ a1, 2 · ai ≤ ai+1, and an ≤ 1018.
Output
Print a single line containing the answer to the problem.
Sample
input | output |
---|
5 100
2 5 10 21 49
| 3
|
Problem Author: Alexey Danilyuk
Problem Source: Petrozavodsk Summer 2018. t.me/umnik_team Contest