问题文

由于我讨厌浪费，所以我只想说想说的话而不说废话。
世界上存在着一种称为背包问题的东西，它考虑的是如何在给定大小的背包中尽可能地装入价值最高的物品，但是这样的考虑是多余的。
无论价值有多高，我都不能容忍背包里有浪费的空间。我讨厌浪费。
现在，在这里有一个大小为 $X$ 的背包和 $N$ 个物品。
第 $i$ 个物品的大小是 $w_i$。关于物品的价值，我觉得考虑也是多余的，所以可以忽略。
有多少种方法可以把物品装进背包，使得背包里没有浪费的空间呢？
换句话说，从 $N$ 个物品中，有多少种选择方式，使得它们的大小总和正好为 $X$ 呢？
起初我试图用手解决这个问题，但我发现这是一种浪费时间的方法，所以我决定向你求助。
请编写一个没有浪费计算时间的程序来解决这个问题，并帮助我节省我的宝贵时间。

输入

输入以以下格式从标准输入中给出。

$N$ $X$ $w_1$ $w_2$ : $w_N$

• 第 1 行包含两个整数，分别表示物品的数量 $N (1 \\leq N \\leq 32)$ 和背包的大小 $X (1 \\leq X \\leq 10^9)$。
• 第 2 行到第 $N$ 行给出了物品的大小。其中第 $i$ 行（$1 \\leq i \\leq N$）包含一个整数 $w_i (1 \\leq w_i \\leq 5 \\times 10^7)$，表示第 $i$ 个物品的大小。

输出

输出一个整数，表示从 $N$ 个物品中选择一些物品，使得它们的大小之和恰好为 $X$ 的方法数。

输入例子1

5 5
1
1
2
3
4

输出例子1

4

没有浪费的物品选择方式有以下 4 种：

• 选择物品 1、物品 2 和物品 4：$1 + 1 + 3 = 5$
• 选择物品 1 和物品 5：$1 + 4 = 5$
• 选择物品 2 和物品 5：$1 + 4 = 5$
• 选择物品 3 和物品 4：$2 + 3 = 5$

请注意，物品 1 和物品 2 的重量相同，但是要将它们视为不同的物品。

输入例子2

8 21
10
4
2
30
22
20
8
14

输出例子2

0

无论如何选择物品，它们的大小之和都无法恰好为 21。

输入例子3

20 100000000
35576749
38866484
6624951
39706038
11133516
25490903
14701702
17888322
14423251
32111678
24509097
43375049
35298298
21158709
30489274
37977301
19510726
28841291
10293962
12022699

输出例子3

45

输入例子4

16 8
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1

输出例子4

12870