爬树的甲壳虫

题目描述

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

输入

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

接下来 n 行每行包含两个整数 x_i, y_i, 用一个空格分隔，表示

P_i = \frac{x_i}{y_i} 。

输出

输出一行包含一个整数表示答案，答案是一个有理数，请输出答案对质数 998244353 取模的结果。其中有理数 \frac{a}{b} 对质数 P 取模的结果是整数 c 满足 0 \leq c 且 c \cdot b \equiv a\pmod P 。

样例

提示

对于 20 \% 的评测用例, n \leq 2,1 \leq x_i;

对于 50 \% 的评测用例, n \leq 500,1 \leq x_i;

对于所有评测用例, 1 \leq n \leq 10^5,1 \leq x_i 。