Description

Yc在出完3道题之后,决定把T4交给Tofu。

Tofu看到最近学弟学妹都在学习搜索和图论，所以他决定出一题背包。

题目非常简单:

Tofu有一个背包，以及一些物品，但是背包不足以装下所以东西，需要有所取舍。

给出背包的容积和 每个物品的体积，试求：如果物品总体积不超过背包容积，他有多少种装物品的方案。如果存在以其中一种方案装入某个物品而另一种方案不装入，则认为这两种方案不同。

Input Format

第一行，两个正整数 $N$ 和 $M(1 \leq N \leq 40,1 \leq M \leq 10^{18})$，表示物品的个数和 Tofu 那背包的容积。

第二行，$N$ 个以空格分隔的正整数，均不超过 $10^{16}$，代表每个物品的体积。

Output Format

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

Sample

样例输入

5 1000
100 1500 500 500 1000

样例输出

8

样例解释

八种方案分别是：

• 一个都不放，溜了溜了
• 体积 $100$ 的物品
• 第一个体积 $500$ 的物品
• 第二个体积 $500$ 的物品
• 体积 $100$ 的物品和第一个体积 $500$ 的物品
• 体积 $100$ 的物品和第二个体积 $500$ 的物品
• 两个体积 $500$ 的物品
• 体积 $1000$ 的物品

Hint

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

$注意时间限制$

$scanf保平安$