当前没有测试数据。

Ex - Inv(0,1)ving Insert(1,0)n

Score : $600$ points

Problem Statement

We have a sequence $A$ consisting of integer pairs. Initially, $A = ( (0, 1), (1, 0) )$.

You may perform the following operation on $A$ as many (possibly zero) times as you want:

• choose adjacent two integer pairs $(a, b)$ and $(c, d)$, and insert $(a + c, b + d)$ between them.

For a sequence $T$ consisting of integer pairs, let us define $f(T)$ as follows:

• let $f(T) =$ (the minimum number of operations required to make every element of $T$ contained in $A$).
  • We say that "every element of $T$ is contained in $A$" if, for all elements $x$ contained in $T$, $x$ is contained in (the set consisting of the elements contained in $A$).
• Here, if there are no such operations, let $f(T) = 0$.

There is a sequence $S = ((a_1, b_1), (a_2, b_2), \dots, (a_N, b_N))$ consisting of $N$ integer pairs. Here, all elements of $S$ are pairwise distinct.
There are $\frac{N \times (N+1)}{2}$ possible consecutive subarrays $S_{l,r}=((a_l,b_l),(a_{l+1},b_{l+1}),\dots,(a_r,b_r))$ of $S$. Find the sum, modulo $998244353$, of $f(S_{l,r})$ over those subarrays.
Formally, find $\displaystyle \sum^{N} _ {l=1} \sum^{N} _ {r=l} f(S_{l,r})$, modulo $998244353$.

Constraints

• $1 \le N \le 10^5$
• $0 \le a_i,b_i \le 10^9$
• $a_i \neq a_j$ or $b_i \neq b_j$, if $i \neq j$.

Input

The input is given from Standard Input in the following format:

$N$

$a_1$ $b_1$

$a_2$ $b_2$

$\dots$

$a_N$ $b_N$

Output

Print the answer as an integer.

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

3511324

• $f(S_{1,1})=2$.
  • We can make $((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)$ is originally contained in $A$.
• $f(S_{l,r})=0$ for all $S_{l,r}$ not mentioned above.
  • We can prove that $A$ can never contain $(0,0)$ or $(6,3)$ regardless of operations.

Therefore, the sum of $f(S_{l,r})$ is $2000000030 = 2 \times 10^9 + 30$, whose remainder when divided by $998244353$ is $3511324$.