题目背景

翻译自 CSES-1628 题。

题目描述

给定一个包含 $n$ 个数的数组，求有多少种方法可以从中选择一个子集，使得子集的和为 $x$。

输入格式

第一行包含两个整数 $n$ 和 $x$，分别表示数组的大小和要求的和。

第二行包含 $n$ 个整数 $t_1,t_2,\ldots,t_n$，表示数组中的数。

输出格式

输出一个整数，表示可以从数组中选择子集，使得该子集的和等于 $x$ 的方法数。

样例

4 5
1 2 3 2

3

数据范围

• $1\le n \le 40$
• $1 \le x \le 10^9$
• $1 \le t_i \le 10^9$