分数插入

题目描述

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

你可以对 $A$ 执行以下操作任意次(包括 $0$ 次):

选择相邻的两个整数对 $(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$ 共有 $\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$ 取模。

输入格式

输入按以下格式从标准输入给出:

$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))$ 得到。

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

数据范围

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