[SNOI2017]遗失的答案

题目描述

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

输入输出格式

输入格式


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

输出格式


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

输入输出样例

输入样例 #1

5 1 30
5
1 2 3 4 5

输出样例 #1

1
2
2
0
2

说明

$\text{30}\%$ 的数据:$\text{N} \le 20$ $\text{50}\%$ 的数据:$\text{N} \le 1000$ $\text{70}\%$ 的数据:$\text{N} \le 100000$ $\text{100}\%$ 的数据:$\text{N, G, L} \le 10^8, \text{Q} \le 10^5, 1 \le \text{X} \le 10^8$