题目描述

给定正整数 $n$，定义 $f(x) = \sum_{a=1}^n\sum_{b=1}^n[ab \equiv x \pmod {n}]$。给定正整数 $K$，定义整数序列 $a_1,a_2,\cdots,a_K$ 的权值为 $\prod_{i=1}^Kf(a_i)$。对于 $r \in [0,n-1]$，定义 $g(r)$ 为所有长度为 $K$，值域为 $0,1,\cdots,n - 1$，且 $\sum_{i=1}^ka_i \equiv r \pmod{n}$ 的序列的权值之和。

你需要回答三个问题：

1. 求出 $\sum_{i=0}^ng(i)$

2. 求出 $\sum_{i=0}^{n-1}g(i)\cdot 3^i$

3. 给定 $Q$ 以及 $x_1,x_2,\cdots,x_Q$，分别求出 $g(x_1),g(x_2),\cdots,g(x_Q)$。

所有问题的答案均对 $10^9 + 7$ 取模。

输入格式

正整数 $n$ 以特殊的方式给出。

第一行，一个正整数 $m$，表示 $n$ 的素因子个数。

接下来 $m$ 行：每行两个正整数 $p_i,c_i$。表示 $n = \prod_{i=1}^{n}p_i^{c_i}$。

第 $m+2$ 行：一个正整数 $K$。

第 $m+3$ 行：一个正整数 $Q$。

接下来 $Q$ 行，每行一个正整数 $x_i$。

输出格式

第一行：一个整数，表示问题 1 的答案。 第二行：一个整数，表示问题 2 的答案。 接下来 $Q$ 行：每行一个整数。表示问题 3 的答案。

样例

样例输入 1

2
2 2
3 1
2
5
0
1
2
3
4

样例输出 1

20736
355911936
2904
1152
1728
1584
2112

样例输入 2

3
2 3
3 3
5 2
10
5
0
1
2
3
4

样例输出 2

684200579
533225646
239561015
44505898
532874077
329728910
805312298

评分方式

如果输出第一行正确，则获得 $30 \%$ 的分数。 如果输出第二行正确，则获得另外 $40 \%$ 的分数。 如果输出第三至 $Q + 2$行都正确，则获得另外 $30 \%$ 的分数。

请务必保证输出恰好 $Q + 2$ 行。

数据范围

对于所有数据，满足 $2 \leq p_i < 10^9$，$p_i$ 为素数且互不相同，

$1 \leq c_i,\prod_{i=1}^m(c_i + 1),Q \leq 3 \times 10^5,1 \leq K < 10^{3 \times 10^5},0 \leq x_i < \min(n,10^{18})$