题目描述

现有 $n$ 种面额两两不同的纸币，面额依次为 $a_1,a_2,\dots,a_n$，每种的数量均无限。请计算有多少种纸币组合可以恰好支付金额 $w$，并将结果对 $10^9+7$ 取模。

本题不区分支付顺序，只要各面额纸币的使用张数相同，就属于同一种组合。

输入格式

第一行给出两个正整数 $n$ 和 $w$，分别表示面额种数与目标金额。

第二行给出 $n$ 个正整数 $a_i$，表示各个面额。

输出格式

输出组合总数对 $10^9+7$ 取模后的值。

6 15
1 5 10 20 50 100

6

3 15
1 5 11

5

数据范围

• $40\%$ 的数据：$n\le 10$，$w\le 100$。
• 全部数据：$1\le n\le 10^3$，$1\le a_i,w\le 10^4$。
• 所有面额两两不同。