Coin Change: Number of Ways to Make Change

Given a target amount \(A\) and a list of coin denominations, your task is to compute the number of unique ways to make change for \(A\). Each coin denomination may be used an unlimited number of times. The order of coins does not matter.

The recurrence relation used in the dynamic programming solution is given by:

\(dp[i] += dp[i - coin]\) for each coin such that \(coin \leq i\).

For example, if \(A = 5\) and the coin denominations are \([1, 2, 5]\), then there are 4 ways to form the amount 5.

inputFormat

The input is read from standard input (stdin) and consists of three lines:

1. The first line contains an integer \(A\) representing the target amount.
2. The second line contains an integer \(n\) denoting the number of coin denominations.
3. The third line contains \(n\) space-separated integers representing the coin denominations.

outputFormat

Output to standard output (stdout) a single integer representing the number of unique ways to make change for the given amount \(A\) using the provided denominations.

5
3
1 2 5

4