Description

After calculating the answer, Little Ball bought a bunch of skins. He was very happy, but by accident, he forgot which skins he had bought. = =|||

Fortunately, he still remembers that he numbered all skins from $1 \sim \text{N}$. Among the skins he bought (he bought at least one skin), the greatest common divisor is $\text{G}$, and the least common multiple is $\text{L}$.

Now there are $\text{Q}$ queries. Each query gives a number $\text{X}$. Please tell Little Ball: among all valid purchase plans, how many of them include skin $\text{X}$?

Because the answer is too large, you only need to output the answer $\bmod{10^9+7}$.

Input Format

The first line contains three integers $\text{N, G, L}$, as described.

The second line contains one integer $\text{Q}$, the number of queries.

The third line contains $\text{Q}$ integers, each being the $\text{X}$ asked in a query.

Output Format

For each query, output one integer per line, representing the answer to this query.

5 1 30
5
1 2 3 4 5

1
2
2
0
2

Hint

$30\%$ of the testdata: $\text{N} \le 20$.

$50\%$ of the testdata: $\text{N} \le 1000$.

$70\%$ of the testdata: $\text{N} \le 100000$.

$100\%$ of the testdata: $\text{N, G, L} \le 10^8, \text{Q} \le 10^5, 1 \le \text{X} \le 10^8$.

Translated by ChatGPT 5