题目描述

整数組からなる列 $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$

输出格式

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

题目大意

给定一个由 $N$ 个整数组成的序列 $S=((a_1,b_1),(a_2,b_2),\cdots,(a_N,b_N))$，并且 $S$ 的元素是不同的。 $S$ 的连续子序列 $S_l,r=((a_l,b_l),(a_l+1,b_l+1),...,(a_r,b_r))$ 有 $N×(N+1)\div2$ 个可能。我们需要计算所有 $f(S_l,r)$ 的和，其中 $f(S_l,r)$ 是使 $S$ 的所有元素都包含在 $A$ 中所需的最小操作次数，$A$ 是如下定义的序列： $A = ((0,1),(1,0))$

具体而言，f(S_l,r) = （使得S_l,r的所有元素都包含在A中所需的最小操作次数）。

如果这样的操作不存在，$f(S_l,r) = 0$。

最后，将所得结果取模 $998244353$ 后输出。

输入格式

输入的第一行包含一个整数 $N$。

接下来的 $N$ 行，每行包含两个整数 $a_i$ 和 $b_i$，表示序列 $S$ 中的元素。

输出格式

输出一个整数，表示取模 $998244353$ 后的答案。

数据范围

对于 $30\%$ 的数据，$2 \le N \le 5$； 对于 $100\%$ 的数据，$2 \le N \le 10^3，0 \le a_i, b_i \le 10^9$。

输入输出样例

输入样例：

2
0 1
1 0

输出样例：

3

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

3511324

提示

制約

• $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$ です。