题目描述

今年的 WEC 2025（华丽音游大赛）幸运地在山东举行。@Orange 打算去看看。她不是任何人的粉丝，也没有时间观念。她只是单纯的想去看 Yoshiki 开大歌，然后疯狂嘲讽蕾米打不过 Yoshiki 而 Yoshiki 拿下冠军。如果她有足够的钱，她会去看看其她的 WEC 比赛项目，例如中二节奏、音击、太鼓等。不幸的是，她的压岁钱十分有限，她决定把所有压岁钱都用来买门票。给出 @Orange 的预算和每场比赛的票价，试求：如果总票价不超过预算，她有多少种观赛方案。如果存在以其中一种方案观看某场比赛而另一种方案不观看，则认为这两种方案不同。

输入格式

第一行，两个正整数 $N$ 和 $M(1 \leq N \leq 40,1 \leq M \leq 10^{18})$，表示比赛的个数和 @Orange 那只够打 300 pc 的压岁钱。

第二行，$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$ 的比赛

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