题目描述

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

输入格式

输入第一行包含一个整数 n 表示树的高度。 接下来 n 行每行包含两个整数xi, yi，用一个空格分隔，表示Pi = xi/yi。 20%的测试数据：1≤n≤2，1≤xi<yi≤20; 50%的测试数据：1≤n≤500，1≤xi<yi<200； 100%的测试数据：1≤n≤100000，1≤xi<yi≤10^9。

输出格式

输出一行包含一个整数表示答案，答案是一个有理数，请输出答案对质数 998244353 取模的结果。 其中有理数 a/b 对质数 P 取模的结果是整数 c 满足0 ≤ c < P 且c · b ≡ a (mod P)。

输入样例

样例1：
1
1 2

样例2：
3
1 2
3 5
7 11

输出样例

样例1：
2

样例2：
623902744