A22516.纸币问题 2
普及-
通过率:0%
时间限制:1.00s
内存限制:512MB
题目描述
你是一个非常有钱的小朋友。你有 n 种面额互不相同的纸币,第 i 种纸币的面额为 ai 并且有无限张,现在你需要支付 w 的金额,求问有多少种方式可以支付面额 w,答案对 109+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
说明/提示
满足 1≤n≤103,1≤ai≤w≤104。