AT_abc444_g [ABC444G] Kyoen

On a two-dimensional coordinate plane, there is a circle with center at point $ (\frac{A}{C}, \frac{B}{C}) $ and radius $ \frac{\sqrt{N}}{C} $ . Find the number, modulo $ 998244353 $ , of lattice points on the circumference of this circle. $ N $ is given in its prime factorization form as $ N=\prod_{i=1}^{M} P_i^{E_i} $ .

The input is given from Standard Input in the following format: > $ A $ $ B $ $ C $ $ M $ $ P_1 $ $ E_1 $ $ P_2 $ $ E_2 $ $ \vdots $ $ P_M $ $ E_M $

Output the answer.

### Sample Explanation 1 As shown in the figure below, there are $ 12 $ lattice points on the circumference.  ### Sample Explanation 2 As shown in the figure below, there are $ 4 $ lattice points on the circumference.  ### Sample Explanation 3 As shown in the figure below, there are $ 6 $ lattice points on the circumference.  ### Sample Explanation 4 Find the number modulo $ 998244353 $ . ### Constraints - $ N \geq 1 $ - $ 2 \leq P_i \leq 100 $ - $ P_i $ are distinct primes. - $ 1 \leq E_i \leq 10^{18} $ - $ 1 \leq C \leq 50 $ - $ 0 \leq A,B \lt C $ - All input values are integers.