题目描述

小林收集了 $n$ 张纪念卡，编号依次为 $1,2,\ldots,n$。第 $i$ 张卡片的积分为 $a_i$。

小林想从这些卡片中选出若干张，使它们的积分总和恰好为 $T$。每张卡片最多选择一次。

请你计算一共有多少种选择方案。答案可能很大，请输出答案对 $1000000007$ 取模后的结果。

两种方案不同，当且仅当它们选中的卡片编号集合不同。选择卡片的先后顺序不影响方案，但积分相同、编号不同的卡片仍需分别考虑。

可以不选择任何卡片。当 $T=0$ 时，空集是唯一的合法方案；如果没有合法方案，答案为 $0$。

输入格式

第一行输入两个整数 $n,T$，分别表示卡片数量和目标积分。

第二行输入 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示各张卡片的积分。

输出格式

输出一个整数，表示合法方案数对 $1000000007$ 取模后的结果。

4 3
1 2 2 3

3

2 3
2 4

0

3 0
1 1 2

1

样例解释

样例 1 中，合法方案对应的卡片编号集合分别为 $\{1,2\}$、$\{1,3\}$、$\{4\}$，共有 $3$ 种。第 $2$ 张和第 $3$ 张卡片虽然积分相同，但编号不同，因此前两种方案不同。

样例 2 中，无法选出积分总和为 $3$ 的卡片，答案为 $0$。

样例 3 中，不选任何卡片的空集符合要求，计为 $1$ 种方案。

数据规模与约定

对于 $100\%$ 的数据，$1\le n\le100$，$0\le T\le2000$，$1\le a_i\le2000$。所有输入均为整数。

• 子任务 1（30 分）：保证 $n\le12$ 且 $T\le30$。
• 子任务 2（30 分）：保证 $n\le50$ 且 $T\le500$。
• 子任务 3（40 分）：没有特殊限制。