Unique Coin Combinations

In this problem, you are given several test cases. For each test case, you are provided with an integer (m) representing the number of available coin denominations, a list of (m) distinct coin denominations, and an integer (n) representing the target amount. Your task is to compute the number of unique ways to form the amount (n) using the given denominations. Each coin may be used an unlimited number of times, and the order of coins does not matter. The answer should be computed modulo (10^9 + 7).

The recurrence relation for the coin change problem is given by:
[ \text{dp}(0) = 1, \quad \text{dp}(x) = \sum_{c \in D,; c \le x} \text{dp}(x-c) \quad \text{for } x \ge 1 ]

Your program should read the input from standard input (stdin) and output the results to standard output (stdout), printing the answers for all test cases in order, separated by spaces.

inputFormat

The input begins with an integer (t) representing the number of test cases. Each test case consists of three lines:

1. The first line contains an integer (m), the number of coin denominations.
2. The second line contains (m) space‐separated integers representing the coin denominations.
3. The third line contains an integer (n), the target amount.

All input is read from standard input.

outputFormat

For each test case, print a single number representing the number of unique ways to form the amount (n) using the given coin denominations. If there are multiple test cases, output the answers in the order of input, separated by a single space. The output is written to standard output.## sample

2
3
1 2 5
5
2
2 3
10

4 2