题目描述

给定一个长度为 $n$ 的正整数序列 $a_1,a_2,\ldots,a_n$，以及一个正整数 $k$。

你需要从序列中选择若干个元素，使所选元素的和恰好等于 $k$。每个位置的元素最多选择一次，所选元素不要求在原序列中连续。

若两种选取方案中至少有一个被选中的元素下标不同，则认为这两种方案不同。即使两个元素的数值相同，它们也可以分别被选择。

请计算满足要求的选取方案数。

输入格式

第一行包含两个正整数 $n,k$，分别表示序列的长度和要求的元素和。

第二行包含 $n$ 个正整数 $a_1,a_2,\ldots,a_n$，相邻两个整数之间用一个空格分隔。

输出格式

输出一行一个非负整数，表示满足要求的选取方案数。

若不存在满足要求的方案，输出 $0$。答案不需要取模。

样例 1

4 5
1 2 3 4

2

样例 1 解释

满足要求的下标集合有 $\{1,4\}$ 和 $\{2,3\}$，对应的元素和分别为 $1+4=5$ 和 $2+3=5$。

选择同一组下标时，选择的先后顺序不会产生新的方案。

样例 2

3 2
1 1 1

3

样例 2 解释

可以分别选择下标集合 $\{1,2\}$、$\{1,3\}$、$\{2,3\}$。这三种方案虽然都选出了两个 $1$，但所选下标不同，因此分别计数。

样例 3

2 5
2 4

0

样例 3 解释

非空选取方案的元素和只能为 $2$、$4$ 或 $6$，没有方案的元素和等于 $5$。

数据范围

对于所有测试数据，保证：

• $1\le n\le20$；
• $1\le a_i\le10^9$（$1\le i\le n$）；
• $1\le k\le10^9$。

本题共有 $20$ 个测试点，每个测试点 $5$ 分。

由于 $k$ 为正数，一个元素也不选择的方案不满足要求。