#2257. 「SNOI2017」遗失的答案

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

题目描述

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

输入格式

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

输出格式

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

样例

样例输入

5 1 30
5
1 2 3 4 5

样例输出

1
2
2
0
2

数据范围与提示

30%30\% 的数据:N20N\leq 20
50%50\% 的数据:N1000N\leq 1000
70%70\% 的数据:N100000N\leq 100000
100%100\% 的数据:N,G,L108,Q105,1X108N,G,L\leq 10^8,Q\leq 10^5,1\leq X\leq 10^8

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