题目描述

设 $P$ 是一个严格凸多边形，$V$ 是它的顶点集合。对于任意满足 $|W|\ge 3$ 的顶点子集 $W\subseteq V$，$W$ 的凸包称为 $P$ 的一个子多边形。

现在给定一个特殊的凸多边形 $P$。它有 $4n$ 个顶点，且所有顶点坐标均为整数。你需要求出 $P$ 的所有子多边形的面积之和。

多边形 $P$ 按如下方式构造：

1. 考虑顶点为 $(n,0)$、$(0,n)$、$(-n,0)$、$(0,-n)$ 的正方形（旋转了 $45^\circ$）。其边界上恰好有 $4n$ 个整点。
2. 从其中任意一个整点开始，沿逆时针方向依次将这些整点记为 $T_0,T_1,\ldots,T_{4n-1}$。
3. 任取平面上的一个点作为 $P_0$。
4. 对 $1\le i\le 4n$，令 $P_i=P_{i-1}+T_{i-1}$，其中点的加法按坐标分别相加。
5. 最终的多边形 $P$ 的顶点为 $P_0,P_1,\ldots,P_{4n-1}$。

可以证明，无论构造过程中选择哪个起点以及哪个 $P_0$，最终要求的答案都相同。

设所有子多边形面积之和写成最简分数 $A/B$，其中 $\gcd(A,B)=1$。设 $B^{-1}$ 表示 $B$ 在模 $998244353$ 意义下的乘法逆元，请输出

$A\cdot B^{-1}\bmod 998244353$。

输入格式

输入一行一个整数 $n$。

输出格式

输出一个整数，表示答案对 $998244353$ 取模后的结果。

数据范围

$1\le n\le 125000$。