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.