分数: 675 点
问题陈述
在二维坐标平面上,有一个圆心为点 (\frac{A}{C}, \frac{B}{C}) 和半径 \frac{\sqrt{N}}{C}。 求模数 998244353,该圆圆周上的格点。
N 以其素因式分解形式给出: N=\prod_{i=1}^{M} P_i^{E_i}.
约束
- N \geq 1
- 2 \leq P_i \leq 100
- P_i 是不同的素数。
- 1 \leq E_i \leq 10^{18}
- 1 \leq C \leq 50
- 0 \leq A,B \lt C
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
A B C M P_1 E_1 P_2 E_2 \vdots P_M E_M
输出
输出答案。
示例输入 1
1 1 2 2 2 1 5 2
示例输出 1
12
如下图所示,有 12 圆周上的格点。

示例输入 2
1 5 14 4 2 1 5 1 13 1 17 1
示例输出 2
4
如下图所示,有 4 圆周上的格点。

示例输入 3
1 1 6 3 2 1 5 2 13 1
示例输出 3
6
如下图所示,有 6 圆周上的格点。

示例输入 4
0 0 1 10 97 1000000000000000000 89 1000000000000000000 73 1000000000000000000 61 1000000000000000000 59 1000000000000000000 47 1000000000000000000 31 1000000000000000000 23 1000000000000000000 11 1000000000000000000 5 1000000000000000000
示例输出 4
7885876
求模数 998244353.