题目描述Description

现有数字 n 和 c，使用它们来生成一个无限序列 A ，其中:

A_1=n，A_i= gcd(i,c)+{\textstyle \sum_{j=1}^{i-1}} A_j\ \ (i>1)

gcd(i,c) 表示 i 和 c 的最大公因数。

从该序列中挑出任意数字作和，接着将所有求和得到的结果去重后，求其中的第 k 小。

输入格式Input

第一行为三个整数，n、c 和 q。（1\le n,c,q \le 10^5）

随后 q 行，每行为一个正整数 k 。（1\le k \le 10^{18}）

输出格式Output

输出 q 行，对于询问的每个 k，求第 k 小。

由于结果可能很大，请将结果对 1e9+7 取模后输出。

样例Sample

来源Source