Coin Change: Count the Ways

You are given a total amount and a list of coin denominations. Your task is to determine the number of ways to construct the given amount using an unlimited supply of coins for each denomination. The order in which coins are used does not matter.

The dynamic programming approach can be defined by the following recurrence relation: $$dp[0] = 1$$ and for each coin value $$c$$ and for every amount (i) with (c \leq i), the state transition is given by: $$dp[i] += dp[i-c].$$ Use this recurrence to build up the solution for the target amount.

inputFormat

The input consists of two lines. The first line contains a single integer (\text{amount}), representing the total amount to be constructed. The second line contains space-separated integers, each denoting a coin denomination.

outputFormat

Output a single integer representing the number of ways to form the given amount using the provided coin denominations.## sample

4
1 2 3

4