#2257. 「SNOI2017」遗失的答案

内存限制:512 MiB 时间限制:1400 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: liu_cheng_ao

题目描述

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

输入格式

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

输出格式

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

样例

样例输入

5 1 30
5
1 2 3 4 5

样例输出

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。