题目描述

给定不同面额的硬币和一个总金额。计算可以凑成总金额的硬币组合数。

每一种面额的硬币有无限个。

注意：顺序不同的序列视为同一种组合。例如 $1+2$ 和 $2+1$ 是同一种组合。

输入格式

第一行两个整数 $n$ 和 $amount$，分别表示硬币种类数和总金额。

第二行 $n$ 个整数，表示每种硬币的面额。

输出格式

输出一个整数，表示硬币组合数。

输入输出样例 #1

输入 #1

样例

输入

3 5

输出

1 2 5

输出 #1

4

说明/提示

数据范围

• $1 \le n \le 300$
• $1 \le amount \le 5000$
• $1 \le$ 硬币面额 $\le 5000$
• 答案保证在 32 位有符号整数范围内