Coin Combinations I

题目描述

考虑一个由 n 枚硬币组成的货币系统。每枚硬币都有一个正整数面值。你的任务是计算使用可用硬币组成金额 x 的不同方法数。 例如，如果硬币是 {2,3,5} 且目标和是 9，则有 8 种方法：

输入格式

第一行输入包含两个整数 n 和 x：硬币的数量以及目标金额 x。 第二行包含 n 个互不相同的整数 c_1,c_2,\dots,c_n：每枚硬币的面值。

输出格式

输出一个整数：方法数对 $10^9+7$ 取模的结果。

3 9
2 3 5

8

提示

$1 \le n \le 100$ $1 \le x \le 10^6$ $1 \le c_i \le 10^6$

标签: CSES1635|动态规划|DP

来源

CSES1635|动态规划|DP