题目描述

小禾有 $n$ 种积木，第 $i$ 种积木的长度为 $a_i$。不同种类的积木长度互不相同，每种积木都有无限多块。

她想选出一些积木，使选出的积木长度之和恰好为 $T$。请你计算一共有多少种选择方案。

一种方案由每种积木分别选了多少块决定，不考虑积木的排列顺序。例如，选一块长度为 $2$ 的积木和一块长度为 $3$ 的积木，无论摆放顺序如何，都只算一种方案。每种积木可以不选，也可以选多块。

由于方案数可能很大，请输出方案数对 $1000000007$ 取余后的结果。当 $T=0$ 时，一块积木也不选是一种方案。

输入格式

第一行两个整数 $n,T$，分别表示积木种类数和目标总长度。

第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示每种积木的长度。

输出格式

输出一行一个整数，表示符合要求的方案数对 $1000000007$ 取余后的结果。如果无法恰好凑出长度 $T$，输出 $0$。

3 5
1 2 5

4

2 7
2 4

0

3 0
2 3 5

1

样例解释

样例 1 的四种方案分别为：五块长度 $1$；三块长度 $1$ 和一块长度 $2$；一块长度 $1$ 和两块长度 $2$；一块长度 $5$。

样例 2 中，两种积木的长度都是偶数，无法得到总长度 $7$。

样例 3 中，只有一块积木也不选这一种方案。

数据规模与约定

对于 $100\%$ 的数据，$1\le n\le100$，$0\le T\le2000$，$1\le a_i\le2000$，且所有 $a_i$ 互不相同。

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