该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

无额外样例。

题目描述

有 $N$ 个物品，第 $i$ 个物品的重量为 $W_i$。现在想将一些物品装入到一个背包里，该背包的最大载重量为 $M$。

问：在不超过背包最大载重量的前提下，有多少种不同的装载方案？

两种装载方案不同，当前仅当至少存在一个物品在两种装载方案中的装载情况（装入或不装入）不同。

注：什么也不装入，也算一种装载方案。

输入格式

第一行：两个整数 $N, M$

第二行：$N$ 个整数 $W_i$

输出格式

一个整数，表示方案数。

样例 1 输入

3 100
30 50 100

样例 1 输出

5

样例 1 解释

对于样例，有以下 5 种装载方案：

①　一件不装

②　只装重量 30 的物品

③　只装重量 50 的物品

④　只装重量 100 的物品

⑤　装重量 30 和 50 的物品

样例 2 输入

20 284814362679177
29658819685238 31969097640706 36783897234702 14318267043398 26343125668794 39889478847658 30376979471659 154678129194 11205872302042 10017751178080 52378629096924 56130158233221 17924827677800 10441402631428 51748125003574 18329902100203 2504461844726 11540518871959 10349363152716 23232117000370

样例 2 输出

771504

数据规模

100% 的数据： $1 ≤ N ≤ 40， 1 ≤ M ≤ 10^{18}， 1 ≤ W_i ≤ 10^{16}$ 。

测试数据共分为 10 个子任务，每个子任务满分为 10 分，内包含若干个测试点。具体如下：