[CEOI2015 Day2]世界冰球锦标赛

题目描述

**译自 [CEOI2015](https://ceoi2015.fi.muni.cz/tasks.php) Day2 T1「[Ice Hockey World Championship](https://ceoi2015.fi.muni.cz/day2/eng/day2task1-eng.pdf)」** > 今年的世界冰球锦标赛在捷克举行。Bobek 已经抵达布拉格,他不是任何团队的粉丝,也没有时间观念。他只是单纯的想去看几场比赛。如果他有足够的钱,他会去看所有的比赛。不幸的是,他的财产十分有限,他决定把所有财产都用来买门票。 给出 Bobek 的预算和每场比赛的票价,试求:如果总票价不超过预算,他有多少种观赛方案。如果存在以其中一种方案观看某场比赛而另一种方案不观看,则认为这两种方案不同。

输入输出格式

输入格式


第一行,两个正整数 $N$ 和 $M(1 \leq N \leq 40,1 \leq M \leq 10^{18})$,表示比赛的个数和 Bobek 那家徒四壁的财产。 第二行,$N$ 个以空格分隔的正整数,均不超过 $10^{16}$,代表每场比赛门票的价格。

输出格式


输出一行,表示方案的个数。由于 $N$ 十分大,注意:答案 $\le 2^{40}$。

输入输出样例

输入样例 #1

5 1000
100 1500 500 500 1000

输出样例 #1

8

说明

#### 样例解释 八种方案分别是: - 一场都不看,溜了溜了 - 价格 $100$ 的比赛 - 第一场价格 $500$ 的比赛 - 第二场价格 $500$ 的比赛 - 价格 $100$ 的比赛和第一场价格 $500$ 的比赛 - 价格 $100$ 的比赛和第二场价格 $500$ 的比赛 - 两场价格 $500$ 的比赛 - 价格 $1000$ 的比赛 有十组数据,每通过一组数据你可以获得 10 分。各组数据的数据范围如下表所示: |数据组号|$1-2$|$3-4$|$5-7$|$8-10$| |-|:-:|:-:|:-:|:-:| |$N \leq$|$10$|$20$|$40$|$40$| |$M \leq$|$10^6$|$10^{18}$|$10^6$|$10^{18}$|