当前没有测试数据。

细致不可知的插入操作

得分：600分

问题描述

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

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

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

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

• 定义$f(T)$为使$T$中的每个元素都包含在$A$中所需的最小操作次数。
  • 如果没有这样的操作，则$f(T) = 0$。

现在给定一个由$N$个整数对组成的序列$S = ((a_1, b_1), (a_2, b_2), ..., (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}),...,(a_r,b_r))$。请计算所有这些子数组$S_{l,r}$中的$f(S_{l,r})$的和，对$998244353$取模。

输入

输入以以下格式从标准输入中给出：

$N$

$a_1$ $b_1$

$a_2$ $b_2$

...

$a_N$ $b_N$

输出

输出一个整数，表示答案。

示例

输入1

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

输出1

3511324

【解释】对于每个$S_{l,r}$，其对应的$f(S_{l,r})$的值如下：

• $f(S_{1,1})=2$：我们可以通过插入操作从$((0,1),(1,0))$得到$((0,1),(1,1),(1,0))$，再得到$((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$。