今年冰球世锦赛在捷克举行。Bobek 抵达了布拉格，他想观看一些比赛。他没有任何球队偏好，也没有任何时间限制。如果钱足够多，他本可以观看所有的比赛。遗憾的是，他只有有限的捷克克朗，这些钱全部可以用来购买门票。已知每场比赛的门票价格，请计算他有多少种观看比赛的方案，使得总花费不超过他的预算。如果两种方案中存在一场比赛在其中一种方案里被观看，而在另一种方案里没有被观看，则认为这两种方案是不同的。
输入格式
从标准输入读取 Bobek 的情况。输入的第一行包含两个正整数 $N$ 和 $M$ ($1 \le N \le 40, 1 \le M \le 10^{18}$)，分别表示比赛场数和 Bobek 可以花费的捷克克朗数量。第二行包含 $N$ 个以空格分隔的正整数，每个数均不超过 $10^{16}$，表示各场比赛的门票价格。
输出格式
输出一行，表示 Bobek 观看比赛的方案总数。请注意，由于 $N$ 的限制，该数字最大为 $2^{40}$。
样例
输入 1
5 1000 100 1500 500 500 1000
输出 1
8
说明
这 8 种可能的方案为： 不观看任何比赛 观看价值为 100 的比赛 观看第一场价值为 500 的比赛 观看第二场价值为 500 的比赛 观看价值为 100 的比赛和第一场价值为 500 的比赛 观看价值为 100 的比赛和第二场价值为 500 的比赛 观看两场价值均为 500 的比赛 观看价值为 1000 的比赛
子任务
共有 10 组测试数据，每组 10 分。各组测试数据的 $N$ 和 $M$ 上界如下表所示：
| 组别 | 1–2 | 3–4 | 5–7 | 8–10 |
|---|---|---|---|---|
| $N$ 的上限 | 10 | 20 | 40 | 40 |
| $M$ 的上限 | $10^6$ | $10^{18}$ | $10^6$ | $10^{18}$ |