题目描述

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

本题区分支付顺序：即使使用的纸币完全相同，只要排列顺序不同，也计为不同方案。例如，支付 $3$ 元时，$1+2$ 与 $2+1$ 是两种方案。

输入格式

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

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

输出格式

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

6 15
1 5 10 20 50 100

42

3 15
1 5 11

39

数据范围

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