灵石兑换

题目描述

在神秘的浮空岛上，流通着各种面值的“灵石”。岛上的杂货铺老板有一项神奇的服务：他可以帮你把大额灵石兑换成零散的小额灵石。

已知岛上共有 $N$ 种不同面值的灵石，面值分别为 $v_1, v_2, \dots, v_n$。每种面值的灵石数量都是无限的。

现在你手里有一块总价值为 $M$ 的巨型灵石，你想要计算出，一共有多少种不同的方案，可以将其恰好兑换成这些面值的灵石组合？

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

输入格式

第一行包含两个整数 $N$ 和 $M$，分别表示灵石的面值种类和目标总价值。

接下来的 $N$ 行，每行包含一个整数 $v_i$，表示第 $i$ 种灵石的面值。

输出格式

输出一个整数，表示兑换方案数对 $10^9 + 7$ 取模后的结果。

输入输出样例 #1

输入 #1

3 5
1
2
5

输出 #1

4

样例 1 说明

共有 4 种方案：

1. $1+1+1+1+1$
2. $1+1+1+2$
3. $1+2+2$
4. $5$

输入输出样例 #2

输入 #2

2 10
3
5

输出 #2

1

样例 2 说明

只有一种方案：两颗面值为 5 的灵石。

数据范围

对于 $60\%$ 的数据，$1 \le N \le 100$，$1 \le M \le 1000$。

对于 $100\%$ 的数据，$1 \le N \le 100$，$1 \le M \le 10^4$，$1 \le v_i \le M$。

建议

二刷