问题描述

有一只甲壳虫想要爬上一颗高度为 $n$ 的树，它一开始位于树根，高度为 0，当它尝试从高度 $i-1$ 爬到高度为 $i$ 的位置时有 $P_i$ 的概率会掉回树根，求它从树根爬到树顶时，经过的时间的期望值是多少。

输入格式

输入第一行包含一个整数 $n$ 表示树的高度。

接下来 $n$ 行每行包含两个整数 $x_i, y_i$ ，用一个空格分隔，表示 $P_i = \dfrac{x_i}{y_i}$ 。

输出一行包含一个整数表示答案, 答案是一个有理数, 请输出答案对质数 $998244353$ 取模的结果。

其中有理数 $\frac{a}{b}$ 对质数 $P$ 取模的结果是整数 $c$ 满足 $0 \leq c<P$ 且 $c \cdot b \equiv a(\bmod P)$ 。

1
1 2

623902744

对于 20% 的评测用例, $n \leq 2,1 \leq x_{i}<y_{i} \leq 20$ ;

对于 50% 的评测用例, $n \leq 500,1 \leq x_{i}<y_{i} \leq 200$ ;

对于所有评测用例, $1 \leq n \leq 100000,1 \leq x_{i}<y_{i} \leq 10^{9}$。