Meet in the Middle

时限1s

空间限制512MB

题目描述

给定 n 和一个长度为 n 的数组，有多少种方法选择一个该数组的子集使得和为 x 。

输入

第一行两个整数 n 和 x ，分别为数组的大小和所需子集和 x 。

第二行包含 n 个数，表示给定的数组。

输出

子集和为 x 的方案数

数据范围

1≤n≤40

1≤x≤109

1≤ti≤109

样例

Input:

4 5

1 2 3 2

Output:

3