Stevie: "Math is so much fun". Also, finally a player that is still at Liverpool :

You are given a number K expressed as a product of a given array A of N integers. In short, \( K = \prod_{i=1}^N A[i] \) . Now, in addition, you are also given 2 functions that are :

\( G(i) \) = smallest divisor of number i greater that 1

\( F(i) \) : 0, if \(i=1\).

else \( F(i)\) = \((1 + F(i/G(i))) \)

Now, you need to answer Q queries. In each query, you shall be given a single number Y. You need to find the sum of all numbers X, such that K is divisible by X. and \(F(X)=Y\)

As the answer to this can be rather large, print it Modulo \( 10^9+7 \).

Input Format :

The first line contains 2 space separated integers N and Q. The next line contains N space separated integers, where the \(i^{th}\) integer denotes \(A[i]\).

Each of the next Q lines contains a single integer Y.

Output Format:

Print the answer to each query on a new line Modulo \( 10^9+7 \)

Constraints :

\( 1 \le N \le 5 \times 10^4 \)

\( 1 \le Q \le 10^4 \)

\( 0 \le Y \le 10^4 \)

\( 1 \le A[i] \le 10^5 \)

Worth 40% of the total score :

\( 1 \le N, A[i] ,Y , Q \le 5000 \)