問題文

$2$ 次元ユークリッド空間上の $N$ 頂点凸多角形 $P$ が与えられます。 $P$ の頂点は頂点 $1, 2, \cdots, N$ と番号付けられています。頂点 $i$ $(1\le i \le N)$ は座標 $(X_i, Y_i)$ にあり、 $P$ の辺は頂点 $i$ と頂点 $i+1$ を結ぶ $N$ 個の辺からなります。ただし、頂点 $N+1$ は頂点 $1$ を指すものとします。

$0$ 以上 $1$ 未満の実数を一様ランダムに $2$ つとり、 $p, q$ とします。 $P$ に含まれる点をすべて $(p, q)$ だけ平行移動した多角形

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

の内部に含まれる格子点の個数の期待値を $\mathrm{mod} ~ {998244353}$ で求めてください。

制約

• 入力はすべて整数
• $3 \le N \le 100$
• $P$ は凸多角形である
• $P$ の面積は正である
• $-10^6 \le X_i, Y_i \le 10^6$
• $(X_1, Y_1), \cdots, (X_N, Y_N)$ は $P$ の頂点を（ $x$ 軸の正の向きを右向き、 $y$ 軸の正の向きを上向きとしたときの）反時計回転で与えたものである。
• $(X_i, Y_i), (X_{i+1}, Y_{i+1}), (X_{i+2}, Y_{i+2})$ は一直線上に存在しない。ただし、 $(X_{N+1}, Y_{N+1})$ は $(X_1, Y_1)$ を表し、 $(X_{N+2}, Y_{N+2})$ は $(X_2, Y_2)$ を表す。 $(1 \le i \le N)$

入力

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

出力

サンプル

サンプル1

入力サンプルをコピー

入力

3
1 1
0 2
-1 0

出力

499122178

多角形 $P$ は次のようになります：

多角形 $Q$ に含まれる確率が正である格子点は次の $4$ 点です。

• $(0,1)$： $Q$ の内部に含まれる必要十分条件は $0 \lt a, b \lt 1, 2a-1 \lt b \lt \frac{a}{2}+\frac{1}{2}$ であり、確率は $\frac{1}{2}$ である
• $(0,2)$： $Q$ の内部に含まれる必要十分条件は $0 \lt a \lt \frac{b}{2} \lt 1$ であり、確率は $\frac{1}{4}$ である
• $(1,1)$： $Q$ の内部に含まれる必要十分条件は $0 \lt b \lt \frac{a}{2} \lt 1$ であり、確率は $\frac{1}{4}$ である
• $(1,2)$： $Q$ の内部に含まれる必要十分条件は $0 \lt a, b \lt 1, 1 \lt a+b$ であり、確率は $\frac{1}{2}$ である

以上より、 $Q$ の内部に含まれる格子点の個数の期待値は $\frac{3}{2}$ であることが分かります。 $2 \times 499122178 \equiv 3 \pmod{998244353}$ であるため、 $499122178$ を出力します。

サンプル2

入力サンプルをコピー

入力

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

出力

68155167

多角形 $P$ は次のようになります：