题目描述

某国家有 $n$ 种不同面值的货币，第 $i$ 种货币价值 $a_i$ 元。请问：如果每种货币都提供任意多的数量的情况下，凑出 $m$ 元金额的货币，有多少种不同的方案？

注意：方案不考虑顺序，例如 $1+2$ 和 $2+1$ 视为同一种方案。

输入格式

第一行：两个整数 $n, m$（$1 \le n \le 100$，$1 \le m \le 5000$）；

以下 $n$ 行：每行一个整数，第 $i+1$ 行为第 $i$ 种货币的面值 $a_i$（$1 \le a_i \le m$）。

输出格式

仅一行，一个整数，表示不同的方案数（题目保证方案数 $\le 10^{18}$）。

输入输出样例

输入 #1

3 10
1
2
5

输出 #1

10

样例解释

凑出10元的10种方案如下：

1. $1+1+1+1+1+1+1+1+1+1$
2. $1+1+1+1+1+1+1+1+2$
3. $1+1+1+1+1+1+2+2$
4. $1+1+1+1+2+2+2$
5. $1+1+2+2+2+2$
6. $2+2+2+2+2$
7. $1+1+1+1+1+5$
8. $1+1+1+2+5$
9. $1+2+2+5$
10. $5+5$