AT_abc444_g [ABC444G] Kyoen

在二维坐标平面上，有一个圆，其圆心在点 $(\frac{A}{C}, \frac{B}{C})$，半径为 $\frac{\sqrt{N}}{C}$。请你求出该圆的周长上有多少个整点，并对 $998244353$ 取模。 $N$ 已经按照其质因数分解的形式给出，即 $N = \prod_{i=1}^{M} P_i^{E_i}$。

输入从标准输入中获得，格式如下： > $A\ B\ C\ M\ P_1\ E_1\ P_2\ E_2\ \cdots\ P_M\ E_M$

输出答案。

### 样例解释 1 如下图所示，该圆周长上有 $12$ 个整点。  ### 样例解释 2 如下图所示，该圆周长上有 $4$ 个整点。  ### 样例解释 3 如下图所示，该圆周长上有 $6$ 个整点。  ### 样例解释 4 请将结果对 $998244353$ 取模。 ### 数据范围 - $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 < C$ - 所有输入值均为整数。 由 ChatGPT 5 翻译