CF848E.Days of Floral Colours

The Floral Clock has been standing by the side of Mirror Lake for years. Though unable to keep time, it reminds people of the passage of time and the good old days.

On the rim of the Floral Clock are 2_n_ flowers, numbered from 1 to 2_n_ clockwise, each of which has a colour among all n possible ones. For each colour, there are exactly two flowers with it, the distance between which either is less than or equal to 2, or equals n. Additionally, if flowers u and v are of the same colour, then flowers opposite to u and opposite to v should be of the same colour as well — symmetry is beautiful!

Formally, the distance between two flowers is 1 plus the number of flowers on the minor arc (or semicircle) between them. Below is a possible arrangement with n = 6 that cover all possibilities.

The beauty of an arrangement is defined to be the product of the lengths of flower segments separated by all opposite flowers of the same colour. In other words, in order to compute the beauty, we remove from the circle all flowers that have the same colour as flowers opposite to them. Then, the beauty is the product of lengths of all remaining segments. Note that we include segments of length 0 in this product. If there are no flowers that have the same colour as flower opposite to them, the beauty equals 0. For instance, the beauty of the above arrangement equals 1 × 3 × 1 × 3 = 9 — the segments are {2}, {4, 5, 6}, {8} and {10, 11, 12}.

While keeping the constraints satisfied, there may be lots of different arrangements. Find out the sum of beauty over all possible arrangements, modulo 998 244 353. Two arrangements are considered different, if a pair (u, v) (1 ≤ u, v ≤ 2_n_) exists such that flowers u and v are of the same colour in one of them, but not in the other.

花卉时钟多年来一直矗立在镜湖畔。尽管它无法真正计时，却唤起了人们对时光流逝与往昔美好岁月的回忆。

花卉时钟的圆周上共有 $2n$ 朵花，按顺时针方向编号为 $1$ 至 $2n$，每朵花的颜色均属于全部 $n$ 种可能颜色之一。对每种颜色，恰好有两朵花具有该颜色；且这两朵同色花之间的距离要么不超过 $2$，要么恰好等于 $n$。此外，若花朵 $u$ 与 $v$ 颜色相同，则 $u$ 的对径点（即位置相差 $n$ 的点）与 $v$ 的对径点也必须颜色相同——对称，方显美感！

形式化地，两朵花之间的距离定义为：它们之间劣弧（或半圆）上所含花朵数加 $1$。下图是一个满足所有条件的 $n = 6$ 的可能排列示例：

一种排列的“美感”定义为：所有“与对径点颜色相同的花朵”将圆周分割出的各花段长度之积。换言之，为计算美感，我们先从圆周上移除所有那些颜色与其对径点颜色相同的花朵；然后，美感即为剩余所有连续花段长度的乘积（注意：长度为 $0$ 的花段也计入该乘积）。若不存在任何一朵花与其对径点颜色相同，则美感定义为 $0$。例如，上图排列的美感为 $1 \times 3 \times 1 \times 3 = 9$ —— 对应的花段分别为 $\{2\}$、$\{4,\,5,\,6\}$、$\{8\}$ 和 $\{10,\,11,\,12\}$。

在满足上述所有约束的前提下，可能存在大量不同的排列方式。请计算所有可能排列的美感之和，并对 $998\,244\,353$ 取模。若存在某一对 $(u,\,v)$（其中 $1 \le u,\,v \le 2n$），使得在两个排列中，花朵 $u$ 与 $v$ 在其中一个排列中同色、而在另一个中不同色，则认为这两个排列互不相同。

The first and only line of input contains a lonely positive integer n (3 ≤ n ≤ 50 000) — the number of colours present on the Floral Clock.

输入仅有一行，包含一个单独的正整数 $n$（$3 \leq n \leq 50\,000$）——表示花卉钟上颜色的种类数。

Output one integer — the sum of beauty over all possible arrangements of flowers, modulo 998 244 353.

输出一个整数——所有可能的花朵排列方式的美丽值之和，对 998 244 353 取模。

With n = 3, the following six arrangements each have a beauty of 2 × 2 = 4.

While many others, such as the left one in the figure below, have a beauty of 0. The right one is invalid, since it's asymmetric.

当 $n = 3$ 时，以下六种排列的美观度均为 $2 \times 2 = 4$。

而许多其他排列（例如下图中左侧的排列）美观度为 $0$；右侧的排列则无效，因其不具有对称性。