P2834 纸币问题 3

题目背景

你是一个非常有钱的小朋友。 注意： 本题与《进阶篇》的对应题目在输入格式上略有差异。

题目描述

你有 \(n\) 种面额互不相同的纸币，第 \(i\) 种纸币的面额为 \(a_i\)，并且每种纸币数量无限。现在需要支付金额 \(w\)，请计算有多少种纸币组合能够恰好组成金额 \(w\)。答案对 \(10^9+7\) 取模。

注：这里的"组合"不区分顺序，同一组面额与张数的搭配视为同一种方式。

输入格式

• 第一行包含两个正整数 \(n, w\)，分别表示纸币的种数和目标金额。
• 第二行包含 \(n\) 个以空格分隔的正整数 \(a_1, a_2, \dots, a_n\)，表示各纸币的面额（互不相同）。

输出格式

• 输出一个整数，表示能恰好凑齐金额 \(w\) 的组合数量（对 \(10^9+7\) 取模）。

输入输出样例 #1

输入

6 15
1 5 10 20 50 100

输出

6

输入输出样例 #2

输入

3 15
1 5 11

输出

5

说明/提示

• 对于 \(40%\) 的数据，满足 \(n \le 10\)，\(w \le 100\)；
• 对于 \(100%\) 的数据，满足 \(1 \le n \le 10^3\)，\(1 \le a_i, w \le 10^4\)。

（其实小朋友并不有钱。）