Problem Description

A beetle wants to climb a tree of height $n$. It starts at the root, at height $0$. When it tries to climb from height $i-1$ to height $i$, it falls back to the root with probability $P_{i}$. Find the expected time it takes to climb from the root to the top of the tree.

Input Format

The first line contains an integer $n$, the height of the tree.

The next $n$ lines each contain two integers $x_{i}, y_{i}$, separated by a space, meaning $P_{i}=\frac{x_{i}}{y_{i}}$.

Output Format

Output one line containing one integer, representing the answer. The answer is a rational number; output its value modulo the prime $998244353$. For a rational number $\frac{a}{b}$, its value modulo a prime $P$ is the integer $c$ such that $0 \leq c<P$ and $c \cdot b \equiv a\pmod P$.

1
1 2

2

3
1 2
3 5
7 11

623902744

Hint

Constraints:

For $20\%$ of the testdata, $n \leq 2$, $1 \leq x_{i}<y_{i} \leq 20$.

For $50\%$ of the testdata, $n \leq 500$, $1 \leq x_{i}<y_{i} \leq 200$.

For all testdata, $1 \leq n \leq 10^5$, $1 \leq x_{i}<y_{i} \leq 10^{9}$.

Lanqiao Cup 2022 NOI Qualifier A Group, Problem E.

Translated by ChatGPT 5