It is 23:00, and you have finally finished all your deadlines. You decide to play a game to relax. You notice that the ranked ladder is about to reset, so you decide to quickly reach the "minimum guarantee" (a rank floor).

You currently have 0 stars, and you reach the minimum guarantee when you have $n$ stars. Each game won grants you one star, and each game lost deducts one star. Specifically, when you have 0 stars, no further stars are deducted.

For convenience, we simplify the game process: when you have $i$ stars, your probability of winning is $p_i$. You want to know the expected number of games required to reach the minimum guarantee. For special considerations, you only need to output the result modulo 998244353.

Input

The first line contains an integer $n$, representing the number of stars required for the minimum guarantee.

The next $n$ lines each contain two integers $x_i, y_i$ ($i = 0, 1, \dots, n - 1$), representing the probability $p_i = \frac{x_i}{y_i}$.

Output

Output a single integer representing the result modulo 998244353.

In other words, if the answer can be expressed as a rational number $\frac{p}{q}$, you need to output $d \in [0, 998244353)$ such that $dq \equiv p \pmod{998244353}$.

Examples

Input 1

2
1 2
1 2

Output 1

6

Constraints

• For 30% of the data, $n \le 100$.
• For another 30% of the data, $x_i = 1, y_i = 2$.
• For all data, $1 \le n \le 10^6$, $1 \le x_i \le y_i < 998244353$.