← 返回题目
题库练习 纸币问题 3
← 上一题 下一题 →

A2808 | 纸币问题 3

时间限制1s
内存限制512MB
通过 / 提交0/0

题目描述

你是一个非常有钱的小朋友。你有 $n$ 种面额互不相同的纸币，第 $i$ 种纸币的面额为 $a_i$ 并且有无限张，现在你需要支付 $w$ 的金额，请问有多少种纸币组合能恰好支付金额 $w$，答案对 $10^9+7$ 取模。

输入格式

第一行两个正整数 $n,w$，分别表示纸币的种数和要凑出的金额。
第二行一行 $n$ 个以空格隔开的正整数 $a_1, a_2, \dots a_n$ 依次表示这 $n$ 种纸币的面额。

输出格式

一行一个整数，表示能恰好凑齐面额 $w$ 的纸币组合数量。

输入输出样例

输入 #1
6 15
1 5 10 20 50 100
输出 #1
6
输入 #2
3 15
1 5 11
输出 #2
5
C++ 编辑器
输入
输出