描述 Description
连年征战之后,晋朝一统天下。为了方便各地百姓的交流、通商,皇上下令建立新的货币系统。财政大臣提出了多种方案供选择。为了得到最好的方案,皇上想知道有多少种不同的方法可以用货币系统中的货币来构造一个确定的数值。
举例来说, 使用一个货币系统 {1,2,5,10}产生 18单位面值的一些可能的方法是:18x1, 9x2, 8x2+2x1, 3x5+2+1,等等其它。
输入格式 Input Format
第一行:两个整数v,n。v表示货币系统中货币的种类数目,n表示要构造的钱的数目。
1<=v<=25,1<= n<=10,000
第二行:v个整数,表示系统中所有货币的面值。
输出格式 Output Format
单独的一行包含用这v种货币构造n的钱的总方案数。保证总数将会适合Int64 (Free Pascal),即在0 到2^63-1之间。
样例输入 Sample Input
3 10
1 2 5
样例输出 Sample Output
10
样例解释:就是10=x+2y+5z有10组非负整数解 |