AT_abc444_g [ABC444G] Kyoen
Description
2 次元座標平面に、 点 $ (\frac{A}{C}, \frac{B}{C}) $ を中心とする半径 $ \frac{\sqrt{N}}{C} $ の円があります。 この円の円周上にある格子点の個数を $ 998244353 $ で割ったあまりを求めてください。
なお、 $ N $ は $ N=\prod_{i=1}^{M} P_i^{E_i} $ と素因数分解された形で与えられます。
Input Format
入力は以下の形式で標準入力から与えられる。
> $ A $ $ B $ $ C $ $ M $ $ P_1 $ $ E_1 $ $ P_2 $ $ E_2 $ $ \vdots $ $ P_M $ $ E_M $
Output Format
答えを出力せよ。
Explanation/Hint
### Sample Explanation 1
下図に示す通り、円周上に $ 12 $ 個の格子点があります。
### Sample Explanation 2
下図に示すとおり、円周上に $ 4 $ 個の格子点があります。
### Sample Explanation 3
下図に示すとおり、円周上に $ 6 $ 個の格子点があります。
### Sample Explanation 4
$ 998244353 $ で割った余りを求めてください。
### Constraints
- $ 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 $
- 入力は全て整数