题目描述

仓库里有 $n$ 个砝码，第 $i$ 个砝码重 $w_i$ 克。要从里面挑出若干个（可以一个都不挑），使挑出的砝码总重量恰好等于 $T$ 克。

求有多少种不同的挑法。两种挑法不同，当且仅当被挑出的砝码编号集合不同。

输入格式

第一行两个整数 $n,T$。

第二行 $n$ 个整数 $w_i$。

输出格式

一行一个整数，表示挑法数。

输入输出样例 #1

输入 #1

5 5
1 2 3 4 5

输出 #1

3

说明

数据范围

• 对于 $100\%$ 的数据，$1\le n\le 40$，$1\le w_i\le 10^9$，$0\le T\le 10^{12}$。答案不超过 $2^{40}$，用 64 位整数存储不会溢出。

样例说明：挑法分别是 $\{5\}$、$\{1,4\}$、$\{2,3\}$，共 $3$ 种。