配点 : $600$ 点

問題文

整数組からなる列 $A$ があります。はじめ $A = ( (0, 1), (1, 0) )$ です。

あなたは $A$ に対して次の操作を $0$ 回以上何度でも行うことができます。

• 隣り合う $2$ つの整数組 $(a, b), (c, d)$ を自由に選び、その間に $(a + c, b + d)$ を挿入する。

整数組の列 $T$ について、 $f(T)$ を以下のように定義します。

• $f(T) =$ ( $T$ の要素がすべて $A$ に含まれる状態になるまでに必要な最小の操作回数 ) とする。- 「 $T$ の要素がすべて $A$ に含まれる状態」とは、全ての $T$ に含まれる要素 $x$ について、 $x$ が ( $A$ に含まれる要素の集合 ) に含まれることを指す。
• 「 $T$ の要素がすべて $A$ に含まれる状態」とは、全ての $T$ に含まれる要素 $x$ について、 $x$ が ( $A$ に含まれる要素の集合 ) に含まれることを指す。
• ただし、そのような操作が存在しない場合 $f(T) = 0$ とする。

$N$ 個の整数組からなる列 $S = ((a_1, b_1), (a_2, b_2), \dots, (a_N, b_N))$ があります。また、 $S$ の要素は相異なります。 $S$ の連続部分列 $S_{l,r}=((a_l,b_l),(a_{l+1},b_{l+1}),\dots,(a_r,b_r))$ として考えられるものは $\frac{N \times (N+1)}{2}$ 通りありますが、それらに対する $f(S_{l,r})$ の総和を $998244353$ で割った余りを求めてください。 より正確には、 $\displaystyle \sum^{N} _ {l=1} \sum^{N} _ {r=l} f(S_{l,r})$ を $998244353$ で割った余りを求めてください。

制約

• $1 \le N \le 10^5$
• $0 \le a_i,b_i \le 10^9$
• $i \neq j$ ならば、 $a_i \neq a_j$ または $b_i \neq b_j$

入力

入力は以下の形式で標準入力から与えられる。

$N$

$a_1$ $b_1$

$a_2$ $b_2$

$\dots$

$a_N$ $b_N$

出力

答えを整数として出力せよ。

7
1 2
3 7
3 5
0 0
1000000000 1
0 1
6 3

3511324

• $f(S_{1,1})=2$ です。- $((0,1),(1,0)) \rightarrow ((0,1),(1,1),(1,0)) \rightarrow ((0,1),(1,2),(1,1),(1,0))$ と操作をすればよいです。
• $((0,1),(1,0)) \rightarrow ((0,1),(1,1),(1,0)) \rightarrow ((0,1),(1,2),(1,1),(1,0))$ と操作をすればよいです。
• $f(S_{1,2})=5$ です。
• $f(S_{1,3})=7$ です。
• $f(S_{2,2})=5$ です。
• $f(S_{2,3})=7$ です。
• $f(S_{3,3})=4$ です。
• $f(S_{5,5})=1000000000 = 10^9$ です。
• $f(S_{5,6})=1000000000 = 10^9$ です。
• $f(S_{6,6})=0$ です。- $(0,1)$ は元から $A$ に含まれています。
• $(0,1)$ は元から $A$ に含まれています。
• 上述されていない $S_{l,r}$ について、 $f(S_{l,r})=0$ です。- $A$ にどのように操作を行っても、 $(0,0)$ や $(6,3)$ が含まれる状態にはできないことが証明できます。
• $A$ にどのように操作を行っても、 $(0,0)$ や $(6,3)$ が含まれる状態にはできないことが証明できます。

以上より、 $f(S_{l,r})$ の総和は $2000000030 = 2 \times 10^9 + 30$ であり、それを $998244353$ で割った余りは $3511324$ です。