Coin Combinations

You are given a set of coin denominations and a target amount. Your task is to determine the number of distinct combinations of coins that sum up to the target amount. You may use each coin denomination an unlimited number of times.

The problem can be formulated using dynamic programming. Define a function \(dp(x)\) as the number of ways to form the amount \(x\). The recurrence relation for each coin denomination \(c\) is:

$$dp(x) = dp(x) + dp(x-c) \quad \text{for } x \ge c$$

with the base case \(dp(0) = 1\) (there is exactly one way to form amount 0: by choosing no coins).

inputFormat

The input is provided via standard input (stdin) in the following format:

1. The first line contains an integer \(n\) representing the number of coin denominations.
2. The second line contains \(n\) space-separated integers, denoting the coin denominations. If \(n = 0\), this line will be empty.
3. The third line contains a single integer representing the target amount.

outputFormat

Output a single integer via standard output (stdout) representing the number of ways to form the target amount using the given coin denominations.

3
1 2 5
5

4