给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
输入描述:
第一行两个个整数N和K， N代表需要达到的总金额，K代表有K种面额的硬币，用空格分隔。第二行为K个整数a1,a2...ak，用空格分隔，代表K种面额的硬币。


输出描述:
一个整数代表用所给面额的硬币组合成N的方案数。
示例1

输入

5 3
1 2 5

输出

4

说明

5 = 5

5 = 2 + 2 + 1

5 = 2 + 1 + 1 + 1

5 = 1 + 1 + 1 + 1 + 1

备注:
01因为结果很大，请将其对1e9+7(1000000007)取模
加载中...