Skin Purchase Schemes

A little ball bought a bunch of cosmetic skins. He numbered all skins from 1 to N. Unfortunately, after computing an answer he was so happy that he bought many skins, but he accidentally forgot which skins he bought! Luckily, he still remembers that:

• The skins are numbered from 1 to N.
• He bought at least one skin.
• If we collect the numbers of the skins he bought, their greatest common divisor is \(G\) and their least common multiple is \(L\).

Now, there are \(Q\) queries. In each query a number \(X\) is given. Please tell him in how many legal purchase schemes (i.e. subsets of {1, 2, \(\dots\), N} meeting the conditions) the skin numbered \(X\) is bought. Since the answer may be very large, output it modulo \(10^9+7\).

Note: A skin can only be bought if it can possibly appear in a valid scheme. In any valid scheme, every purchased skin must be a multiple of \(G\) and a divisor of \(L\). In other words, if we let \(M = \frac{L}{G}\), then every purchased skin has the form \(d\cdot G\) where \(d\) is a divisor of \(M\) and \(d\cdot G \le N\>.

inputFormat

The first line contains four integers \(N, G, L, Q\) separated by spaces.

Then \(Q\) lines follow; each line contains a single integer \(X\), representing a query.

Constraints:

• \(1 \le G \lt L \le N \le 10^9\)
• \(1 \le Q \le 10^5\)
• It is guaranteed that \(L\) is a multiple of \(G\).

outputFormat

For each query output one line containing a single integer: the number of valid purchase schemes in which skin \(X\) is bought, modulo \(10^9+7\).

sample

30 2 30 3
2
10
30

6
3
6