Coin Change Problem

You are given a set of coin denominations and a target amount \(M\). Your task is to determine the number of distinct ways to form the sum \(M\) using the given coins. There is an unlimited supply of each type of coin.

The problem can be modeled using dynamic programming. Let \(dp[i]\) represent the number of ways to form the amount \(i\). The recurrence relation is given by:

[ dp[i] = \sum_{\text{coin} \le i} dp[i - \text{coin}] ]

with the base case \(dp[0] = 1\), representing the one way to have a sum of 0 (by selecting no coins). Your solution must compute \(dp[M]\) based on these rules.

inputFormat

The input is read from the standard input (stdin) and is formatted as follows:

• The first line contains an integer \(N\), representing the number of coin denominations.
• The second line contains \(N\) space-separated integers, each representing a coin denomination.
• The third line contains an integer \(M\), representing the target amount.

outputFormat

Output a single integer to the standard output (stdout) — the number of distinct ways to form the amount \(M\) using the given coins.

## sample

3
1 2 5
5

4

</p>