← 返回题目列表

AtCoder · abc444_g

G. 京炎

中文机器翻译题面 查看原题

分数: 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 圆周上的格点。

Figure


示例输入 2

1 5 14 4
2 1
5 1
13 1
17 1

示例输出 2

4

如下图所示,有 4 圆周上的格点。

Figure


示例输入 3

1 1 6 3
2 1
5 2
13 1

示例输出 3

6

如下图所示,有 6 圆周上的格点。

Figure


示例输入 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.