Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 3940
Modulo Query

Time Limit: 2 Seconds      Memory Limit: 65536 KB

One day, Peter came across a function which looks like:

  • F(1, X) = X mod A1.
  • F(i, X) = F(i - 1, X) mod Ai, 2 ≤ iN.
Where A is an integer array of length N, X is a non-negative integer no greater than M.

Peter wants to know the number of solutions for equation F(N, X) = Y, where Y is a given number.

Input

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.

Output

For each test cases, output an integer S = (1 ⋅ Z1 + 2 ⋅ Z2 + ... + QZQ) mod (109 + 7), where Zi is the answer for the i-th query.

Sample Input

1
3 5
3 2 4
5
0
1
2
3
4

Sample Output

8

Hint

The answer for each query is: 4, 2, 0, 0, 0.


Author: LIN, Xi
Source: The 13th Zhejiang Provincial Collegiate Programming Contest
Submit    Status