Ice Hockey World Championship

This year the Ice Hockey World Championship was held in the Czech Republic. Bobek has arrived in Prague and wants to watch some of the matches. He has no favourite team and no scheduling constraints, so with enough money he could watch every match. His money is a fixed amount of Czech crowns, and he can spend all of it on tickets.

Given the ticket price of each match, count the ways Bobek can choose a set of matches without exceeding his budget. Two ways are different if some match is watched in one of them and not in the other. Watching no match at all counts as one way.

The first line contains the number of matches $N$ and the amount of money Bobek can spend $M$. ($1 \le N \le 40$, $1 \le M \le 10^{18}$)

The second line contains the $N$ ticket prices separated by spaces. Each price is an integer between $1$ and $10^{16}$.

Print the number of ways on one line. Because of the limit on $N$, this value never exceeds $2^{40}$.

When the prices are $100$, $1500$, $500$, $500$, $1000$ and the budget is $1000$, the eight ways are:

• watch no match
• the match worth $100$
• the first match worth $500$
• the second match worth $500$
• the match worth $100$ and the first match worth $500$
• the match worth $100$ and the second match worth $500$
• both matches worth $500$
• the match worth $1000$