题目描述

给定 $n$ 种硬币，每种硬币有无限多枚，第 $i$ 种硬币的面值为 $c_i$。

现在要用这些硬币凑出总金额 $N$ 元，问一共有多少种不同的组合方式？

注意：组合不考虑顺序。例如 $2+1$ 和 $1+2$ 被视为同一种组合。

输入格式

第一行包含两个整数 $n$ 和 $N$，分别表示硬币种类数和目标金额。

第二行包含 $n$ 个整数 $c_1, c_2, \dots, c_n$，表示每种硬币的面值。

输出格式

输出一个整数，表示不同的组合数。

由于答案可能很大，请输出对 $10^9+7$ 取模后的结果。

样例

3 5
1 2 5

4

样例解释

凑出 $5$ 元的不同组合共有 $4$ 种：

• $5$
• $2+2+1$
• $2+1+1+1$
• $1+1+1+1+1$

数据范围

• $1 \le n \le 100$
• $1 \le N \le 10000$
• $1 \le c_i \le 10000$
• $1 \le c_1 \lt c_2 \lt \ldots \lt c_n$