题目描述

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

输入格式

第一行两个正整数 n,w，分别表示纸币的种数和要凑出的金额。 第二行一行 n 个以空格隔开的正整数 a1,a2,…an依次表示这 n 种纸币的面额。 1≤n≤10^3，1≤ai,w≤10^4

输出格式

一行一个整数，表示支付方式的数量。

样例

输入样例 1

6 15
1 5 10 20 50 100

输出样例 1

42

输入样例 2

3 15
1 5 11

输出样例 2

39

输入样例 3

3 31
1 2 5

输出样例 3

9390983

提示

提示：考虑定义 dp[i]为凑成 i 的方案数，那么显然可得转移方程为 dp[i] = ∑(j=1~n) dp[i-aj]