問題文

N 枚のカードがあります。それぞれのカードには 1 から N の番号がつけられています。blackyuki 君と KoD 君はこのカードを使ってゲームをすることにしました。

blackyuki 君から初めて、全てのカードがなくなるまで交互に以下の操作を繰り返します。

• 残っているカードから 1 枚選ぶ、選んだカードの番号を i とする。
• \frac{A_i}{B_i} の確率でカード i を手に入れ、操作の初めに戻る。
• 1-\frac{A_i}{B_i} の確率で、何もせず操作を終了する。

ゲーム終了時に blackyuki 君の持っているカードの枚数が KoD 君の持っているカードの枚数以上であれば blackyuki 君の勝ち、そうでなければ KoD 君の勝ちとします。

2 人は、以下のように行動します。

• まず、自分がゲーム終了時に持っているカードの枚数の期待値を最大化するようにカードを選ぶ。
• 上記のみでは選ぶカードの候補が複数ある場合、その中で最も番号が小さいカードを選ぶ。

blackyuki 君の勝つ確率 \bmod\ 998244353 を求めてください。

注記

求める確率は必ず有理数となることが証明できます。またこの問題の制約下では、その値を互いに素な 2 つの整数 P,Q を用いて \frac{P}{Q} と表した時、R \times Q \equiv P(\bmod\ 998244353) かつ 0 \le R < 998244353 を満たす整数 R がただ一つ存在することが証明できます。この R を求めてください。

制約

• 入力は全て整数である。
• 1 \le N \le 2 \times 10^5
• 1 \le A_i \le B_i \le 2 \times 10^5

入力例 1

1
1 2

出力例 1

665496236

カード 1 を選び続けるしかありません。blackyuki 君がカード 1 を手に入れる確率は \frac{2}{3} です。

入力例 2

2
1 1
1 1

出力例 2

1

初めに、blackyuki 君がカード 1 を選んだとします。\frac{A_1}{B_1}=1 なので、カード 1 を必ず取ることができます。

そして、blackyuki 君は次にカード 2 を選ぶしかありません。\frac{A_2}{B_2}=1 なので、カード 2 も必ず取ることができます。

ゲーム終了時において、必ず blackyuki 君の持っているカードの枚数が KoD 君の持っているカードの枚数以上であるため、1 を出力します。

入力例 3

8
100660 113169
10964 152336
57329 77239
98640 167660
103515 136455
98695 99571
14421 149410
12488 21041

出力例 3

743177673