题目描述

考虑一个由 $n$ 种硬币组成的货币系统。每个硬币都有一个正整数面值。你的任务是计算使用这些硬币构造出总金额为 $x$ 的不同有序方法的数量。

例如，如果硬币为 $\{2,3,5\}$ 且所需的总金额为 9，有 3 种方法：

• $2 + 2 + 5$
• $3 + 3 + 3$
• $2 + 2 + 2 + 3$

输入格式：

第一行包含两个整数 $n$ 和 $x$：硬币的种类数和所需的金额。 第二行包含 $n$ 个不同的整数 $c_1, c_2, \dots, c_n$，表示每种硬币的面值。

输出格式：

输出一个整数，表示构造总金额为 $x$ 的不同有序方法数，结果对 $10^9 + 7$ 取模。

约束条件：

• $1 \leq n \leq 100$
• $1 \leq x \leq 10^6$
• $1 \leq c_i \leq 10^6$

示例：

输入：

3 9
2 3 5

输出：

3