問題文

長さ $N$ の正整数列 $A,B$ が与えられるので、 $\displaystyle \sum_{i=1}^N \frac{A_i}{B_i}$ を既約分数 $\dfrac{c}{d}$ で表したときの $c,d$ を $998244353$ で割った余りを求めてください。

制約

• $1 \le N \le 2 \times 10^5$
• $1 \le A_i, B_i \le 2 \times 10^5$
• $\gcd(A_i,B_i)=1$
• 入力はすべて整数

入力

$N$
$A_1$ $B_1$
$A_2$ $B_2$
$\vdots$
$A_N$ $B_N$

出力

問題文中で定義される $c,d$ を空白区切りで $1$ 行に出力せよ。

サンプル

2
1 2
2 3

7 6

4
1 4
1 4
1 4
1 4

1 1

2
1 48
1 16

1 12