You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

译自 CEOI2015 Day2 T1「Ice Hockey World Championship」

今年的世界冰球锦标赛在捷克举行。Bobek 已经抵达布拉格，他不是任何团队的粉丝，也没有时间观念。他只是单纯的想去看几场比赛。如果他有足够的钱，他会去看所有的比赛。不幸的是，他的财产十分有限，他决定把所有财产都用来买门票。

给出 Bobek 的预算和每场比赛的票价，试求：如果总票价不超过预算，他有多少种观赛方案。如果存在以其中一种方案观看某场比赛而另一种方案不观看，则认为这两种方案不同。

输入格式

第一行，两个正整数 $N$ 和 $M(1 \leq N \leq 40,1 \leq M \leq 10^{18})$，表示比赛的个数和 Bobek 那家徒四壁的财产。

第二行，$N$ 个以空格分隔的正整数，均不超过 $10^{16}$，代表每场比赛门票的价格。

输出格式

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

样例 #1

样例输入 #1

5 1000
100 1500 500 500 1000

样例输出 #1

8

提示

样例解释

八种方案分别是：

• 一场都不看，溜了溜了
• 价格 $100$ 的比赛
• 第一场价格 $500$ 的比赛
• 第二场价格 $500$ 的比赛
• 价格 $100$ 的比赛和第一场价格 $500$ 的比赛
• 价格 $100$ 的比赛和第二场价格 $500$ 的比赛
• 两场价格 $500$ 的比赛
• 价格 $1000$ 的比赛

有十组数据，每通过一组数据你可以获得 10 分。各组数据的数据范围如下表所示：