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$