P5366 [SNOI2017] Lost Answers

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}$.

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.

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

$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