题目描述

小皮球在计算出答案之后，买了一堆皮肤，他心里很开心，但是一不小心，就忘记自己买了哪些皮肤了。= =|||
万幸的是，他还记得他把所有皮肤按照 $1\sim N$ 来编号，他买来的那些皮肤的编号（他至少买了一款皮肤），最大公约数是 $G$，最小公倍数是 $L$。
现在，有 $Q$ 组询问，每组询问输入一个数字 $X$，请你告诉小皮球，有多少种合法的购买方案中，购买了皮肤 $X$？
因为答案太大了，所以你只需要输出答案 $\bmod 1000000007$ 即可。

输入格式

第一行，三个数字 $N,G,L$，如题意所示。
第二行，一个数字 $Q$，表示询问个数。
第三行，$Q$ 个数字，表示每个询问所问的 $X$。

输出格式

对于每一组询问，在一行中单独输出一个整数，表示这个询问的答案。

样例

input

5 1 30
5
1 2 3 4 5

output

1
2
2
0
2

数据范围与提示

$30\%$ 的数据：$N\leq 20$
$50\%$ 的数据：$N\leq 1000$
$70\%$ 的数据：$N\leq 100000$
$100\%$ 的数据：$N,G,L\leq 10^8,Q\leq 10^5,1\leq X\leq 10^8$

数据范围与原题相同，但测试数据由本站会员自制，并非原数据。
时限已按照评测机速度调整，原题时限为 2000 ms。