P2840 纸币问题 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\)，表示各纸币的面额。

输出格式

• 输出一个整数，表示凑出金额 \(w\) 的方式数（对 \(10^9+7\) 取模）。

输入输出样例 #1

输入

6 15
1 5 10 20 50 100

输出

42

输入输出样例 #2

输入

3 15
1 5 11

输出

39

说明/提示

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