问题描述

我们有一个由整数对组成的序列 $A$。初始时，$A = ((0, 1), (1, 0))$。

你可以对 $A$ 执行以下操作任意次数（包括零次）：

• 选择相邻的两个整数对 $(a, b)$ 和 $(c, d)$，并在它们之间插入 $(a + c, b + d)$。

对于一个由整数对组成的序列 $T$，我们定义 $f(T)$ 如下：

• 令 $f(T) =$ （使 $T$ 中的每个元素都包含在 $A$ 中所需的最小操作数）。
  • 如果对于 $T$ 中包含的每个元素 $x$ ，$x$ 都包含在 $A$ 中的元素组成的集合中，则称" $T$ 中的每个元素都包含在 $A$ 中"。
• 如果不存在这样的操作，则令 $f(T) = 0$。

有一个由 $N$ 个整数对组成的序列 $S = ((a_1, b_1), (a_2, b_2), \dots, (a_N, b_N))$。其中，$S$ 的所有元素两两不同。
$S$ 有 $\\frac{N \\times (N+1)}{2}$ 个可能的连续子数组 $S_{l,r}=((a_l,b_l),(a_{l+1},b_{l+1}),\\dots,(a_r,b_r))$。找出这些子数组上的 $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$

输出

输出一个整数作为答案。

示例输入 1

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

示例输出 1

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))$。
• $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$。