AT_abc273_h [ABC273Ex] Inv(0,1)ving Insert(1,0)n

[problemUrl]: https://atcoder.jp/contests/abc273/tasks/abc273_h 整数組からなる列 $ 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 $ に含まれる要素の集合 ) に含まれることを指す。 - ただし、そのような操作が存在しない場合 $ 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 $ で割った余りを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ a_1 $ $ b_1 $ $ a_2 $ $ b_2 $ $ \dots $ $ a_N $ $ b_N $

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

### 制約 - $ 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 $ ### Sample Explanation 1 \- $ 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)) $ と操作をすればよいです。 - $ 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 $ に含まれています。 - 上述されていない $ S_{l,r} $ について、 $ f(S_{l,r})=0 $ です。 - $ A $ にどのように操作を行っても、 $ (0,0) $ や $ (6,3) $ が含まれる状態にはできないことが証明できます。 以上より、 $ f(S_{l,r}) $ の総和は $ 2000000030\ =\ 2\ \times\ 10^9\ +\ 30 $ であり、それを $ 998244353 $ で割った余りは $ 3511324 $ です。