2365: 【入门】货币问题

内存限制:128 MB 时间限制:1.000 S
评测方式:文本比较 命题人:
提交:0 解决:0

题目描述

某国家有 n 种不同面值的货币,第 i 种货币价值 ai 元。

请问:如果每种货币都提供任意多的数量的情况下,如果需要 m 元金额的货币,有多少种不同的方案?

输入

第一行两个整数 n,m(≤5000,n≤100);

以下 n 行,每行一个整数,第 i+1 行为第 i 种货币的面值。

输出

一个整数,为方案数(方案数≤1018)。

样例输入 复制

3 10
1
2
5

样例输出 复制

10