아이스하키 세계선수권대회

올해 아이스하키 세계선수권대회는 체코에서 열렸다. 프라하에 도착한 보베크는 경기를 몇 개 보려고 한다. 특별히 응원하는 팀도 없고 시간 제약도 없어서, 돈만 넉넉하면 모든 경기를 볼 수 있다. 그러나 보베크가 가진 돈은 정해진 액수의 체코 코루나뿐이고, 이 돈은 전부 입장권을 사는 데 쓸 수 있다.

경기마다 입장권 가격이 주어질 때, 가진 돈을 넘기지 않으면서 볼 경기를 고르는 방법이 몇 가지인지 구하라. 어떤 경기를 한쪽에서는 보고 다른 쪽에서는 보지 않는다면 두 방법은 서로 다르다. 한 경기도 보지 않는 것도 한 가지 방법으로 센다.

첫째 줄에 경기 수 $N$과 보베크가 쓸 수 있는 금액 $M$이 주어진다. ($1 \le N \le 40$, $1 \le M \le 10^{18}$)

둘째 줄에 경기 $N$개의 입장권 가격이 공백으로 구분되어 주어진다. 각 가격은 $1$ 이상 $10^{16}$ 이하의 정수다.

가능한 방법의 수를 한 줄에 출력한다. $N$의 제한 때문에 이 값은 $2^{40}$을 넘지 않는다.

가격이 $100$, $1500$, $500$, $500$, $1000$이고 예산이 $1000$일 때 가능한 방법은 다음 여덟 가지다.

• 한 경기도 보지 않는다
• $100$짜리 경기
• $500$짜리 첫 번째 경기
• $500$짜리 두 번째 경기
• $100$짜리 경기와 $500$짜리 첫 번째 경기
• $100$짜리 경기와 $500$짜리 두 번째 경기
• $500$짜리 경기 두 개
• $1000$짜리 경기