Time Limit: 2 Seconds
Memory Limit: 65536 KB
One day, Peter came across a function which looks like:
Peter wants to know the number of solutions for equation F(N, X) = Y, where Y is a given number.
There are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. For each test case:
The first line contains two integers N and M (2 ≤ N ≤ 105, 0 ≤ M ≤ 109).
The second line contains N integers: A1, A2, ..., AN (1 ≤ Ai ≤ 109).
The third line contains an integer Q (1 ≤ Q ≤ 105) - the number of queries. Each of the following Q lines contains an integer Yi (0 ≤ Yi ≤ 109), which means Peter wants to know the number of solutions for equation F(N, X) = Yi.
For each test cases, output an integer S = (1 ⋅ Z1 + 2 ⋅ Z2 + ... + Q ⋅ ZQ) mod (109 + 7), where Zi is the answer for the i-th query.