P2840 纸币问题 2

你是一个非常有钱的小朋友。

你有 $n$ 种面额互不相同的纸币，第 $i$ 种纸币的面额为 $a_i$ 并且有无限张，现在你需要支付 $w$ 的金额，求问有多少种方式可以支付面额 $w$，答案对 $10^9+7$ 取模。 注意在这里，同样的纸币组合如果支付顺序不同，会被视作不同的方式。例如支付 $3$ 元，使用一张面值 $1$ 的纸币和一张面值 $2$ 的纸币会产生两种方式（$1+2$ 和 $2+1$）。

无

无

对于 $40\%$ 的数据，满足 $n\le 10$，$w\le 100$； 对于 $100\%$ 的数据，满足 $1\le n\le 10^3$，$1\le a_i \le w\le 10^4$。 其实小朋友并不有钱。