该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

T4. 零钱兑换 (change)

题目描述

小明有 $N$ 种不同面值的硬币，第 $i$ 种硬币的面值为 $a_i$。每种硬币都有无限多枚。

小明想用这些硬币凑出恰好 $M$ 元的金额。他想知道，一共有多少种不同的凑法。

两种凑法视为不同，当且仅当存在某一种面值的硬币，在该面值上使用的数量不同。顺序无关。

由于答案可能很大，请输出答案对 $10^9+7$ 取模的结果。

输入格式

第一行两个整数 $N, M$。

第二行 $N$ 个整数 $a_1, a_2, \dots, a_N$，表示每种硬币的面值。

输出格式

一行一个整数，表示凑出金额 $M$ 的方案数模 $10^9+7$。如果无法凑出则输出 $0$。

样例

样例 #1

3 10
1 2 5

10

解释：用面值1,2,5凑10元的方案共10种。

数据范围

对于全部数据，$1\le N\le 100$，$1\le M\le 50000$，$1\le a_i\le M$。