Coin Change Combinations

You are given a set of coin denominations and a target amount \(T\). Your task is to determine the number of different ways to form the target amount using an unlimited supply of coins from the given denominations.

More formally, given coin denominations \(d_1, d_2, \dots, d_n\) and a target \(T\), you must compute the number of nonnegative integer solutions \(x_1, x_2, \dots, x_n\) to the equation \[ d_1 \cdot x_1 + d_2 \cdot x_2 + \cdots + d_n \cdot x_n = T \] Coins can be used an unlimited number of times.

The input consists of multiple test cases. For each test case, an integer \(n\) is given representing the number of denominations, followed by a line with \(n\) space-separated integers denoting the coin values, and then a target amount \(T\). The test cases are terminated by a line containing a single zero.

inputFormat

The input is read from standard input and consists of multiple test cases. Each test case is structured as follows:

1. The first line contains an integer (n) ((n > 0)), the number of coin denominations. A test case starting with 0 indicates the end of input and should not be processed.
2. The second line contains (n) space-separated integers representing the coin denominations.
3. The third line contains an integer (T), the target amount.

All test cases are processed sequentially.

outputFormat

For each test case, output a single line containing the number of ways to form the target amount (T) using the given coin denominations. The result for each test case should be printed on its own line.## sample

3
1 2 3
4
2
5 10
15
0

4
2