Problem Statement

You are given a convex polygon $P$ with $N$ vertices in $2$-dimensional Euclidean space. The vertices of $P$ are numbered as vertices $1, 2, \cdots, N$. Vertex $i$ $(1\le i \le N)$ is located at coordinates $(X_i, Y_i)$, and the edges of $P$ consist of the $N$ edges connecting vertex $i$ and vertex $i+1$. Here, vertex $N+1$ refers to vertex $1$.

Take $2$ real numbers uniformly at random from the range of at least $0$ and less than $1$, and let them be $p, q$. Find the expected value, $\mathrm{mod} ~ {998244353}$, of the number of lattice points contained in the interior of the polygon

$$Q = \{(x+p, y+q) \mid (x, y) \in P\}$$

obtained by translating every point contained in $P$ by $(p, q)$.

Constraints

• All input values are integers.
• $3 \le N \le 100$
• $P$ is a convex polygon.
• The area of $P$ is positive.
• $-10^6 \le X_i, Y_i \le 10^6$
• $(X_1, Y_1), \cdots, (X_N, Y_N)$ are the vertices of $P$ given in counterclockwise order (with the positive direction of the $x$-axis pointing right and the positive direction of the $y$-axis pointing up).
• $(X_i, Y_i), (X_{i+1}, Y_{i+1}), (X_{i+2}, Y_{i+2})$ do not lie on a single straight line. Here, $(X_{N+1}, Y_{N+1})$ denotes $(X_1, Y_1)$ and $(X_{N+2}, Y_{N+2})$ denotes $(X_2, Y_2)$. $(1 \le i \le N)$

Input

$N$
$X_1$ $Y_1$
$\vdots$
$X_N$ $Y_N$

Output

Sample

Sample 1

Input

3
1 1
0 2
-1 0

Output

499122178

The polygon $P$ is as follows:

The lattice points with a positive probability of being contained in the polygon $Q$ are the following $4$ points.

• $(0,1)$: The necessary and sufficient condition for it to be contained in the interior of $Q$ is $0 \lt a, b \lt 1, 2a-1 \lt b \lt \frac{a}{2}+\frac{1}{2}$, and the probability is $\frac{1}{2}$.
• $(0,2)$: The necessary and sufficient condition for it to be contained in the interior of $Q$ is $0 \lt a \lt \frac{b}{2} \lt 1$, and the probability is $\frac{1}{4}$.
• $(1,1)$: The necessary and sufficient condition for it to be contained in the interior of $Q$ is $0 \lt b \lt \frac{a}{2} \lt 1$, and the probability is $\frac{1}{4}$.
• $(1,2)$: The necessary and sufficient condition for it to be contained in the interior of $Q$ is $0 \lt a, b \lt 1, 1 \lt a+b$, and the probability is $\frac{1}{2}$.

From the above, the expected number of lattice points contained in the interior of $Q$ is $\frac{3}{2}$. Since $2 \times 499122178 \equiv 3 \pmod{998244353}$, output $499122178$.

Sample 2

Input

13
541787 -802804
745984 -610628
821010 -469321
148557 920322
-276352 776016
-689247 481241
-955894 130548
-804935 -349606
-374167 -778760
-33915 -920255
5303 -921478
231589 -902268
348969 -873524

Output

68155167

The polygon $P$ is as follows: