纸币问题 2
题目背景
你是一个非常有钱的小朋友。
题目描述
你有 $n$ 种面额互不相同的纸币,第 $i$ 种纸币的面额为 $a_i$ 并且有无限张,现在你需要支付 $w$ 的金额,求问有多少种方式可以支付面额 $w$,答案对 $10^9+7$ 取模。
注意在这里,同样的纸币组合如果支付顺序不同,会被视作不同的方式。例如支付 $3$ 元,使用一张面值 $1$ 的纸币和一张面值 $2$ 的纸币会产生两种方式($1+2$ 和 $2+1$)。
输入输出格式
输入格式
第一行两个正整数 $n,w$,分别表示纸币的种数和要凑出的金额。
第二行一行 $n$ 个以空格隔开的正整数 $a_1, a_2, \dots a_n $ 依次表示这 $n$ 种纸币的面额。
输出格式
一行一个整数,表示支付方式的数量。
输入输出样例
输入样例 #1
6 15
1 5 10 20 50 100
输出样例 #1
42
输入样例 #2
3 15
1 5 11
输出样例 #2
39
说明
对于 $40\%$ 的数据,满足 $n\le 10$,$w\le 100$;
对于 $100\%$ 的数据,满足 $1\le n\le 10^3$,$1\le a_i \le w\le 10^4$。
其实小朋友并不有钱。