Days of Floral Colours

题意翻译

花卉时钟一直矗立在镜湖边。尽管不能留住时间，但它提醒人们时间的过去，使人们想起过去美好的时光。 在花卉时钟的边缘一共有 $2n$ 朵花，顺时针依次编号为 $1$ 到 $2n$，每一朵花的颜色为 $n$ 种可能的颜色中的一种。对于每种颜色，恰有两朵花是这种颜色的，这两朵花的距离要么不大于 $2$，要么等于 $n$。另外，如果花 $u$ 和花 $v$ 有相同的颜色，那么 $u$ 对面的那一朵花和 $v$ 对面的那一朵花的颜色也应该相同——对称是美的！ 形式化的说，两朵花之间的距离是 $1$ 加上夹在以这两朵花为端点的劣弧（或者半圆）之间的花的数目。下面是当 $n=6$ 时一种可能的安排颜色的方式：  我们定义一种安排方式的美感为被所有相对（距离为 $n$）且颜色相同的花分开的连续段的长度的乘积。换句话说，为了计算美感，我们先在环上移除那些与相对的花颜色相同的花。然后，它的美感就是剩下的连续段长度的乘积。注意到本题中包括了长度为 $0$ 的那些连续段。在某种安排方式中，如果没有任何一朵花使得与它相对的花的颜色与它相同，那么这种安排方式的美感为 $0$。比如说，上图的安排方式的美感等于 $1\times 3\times 1\times 3=9$———这些连续段为 $\{2\},\{4,5,6\},\{8\},\{10,11,12\}$。 尽管保持了这些约束条件，但是可能的安排方式会有多种，你需要计算出所有可能的安排方式的美感之和，对 $998244353$ 取模。两个安排方式被视为不同的，当且仅当存在一个二元组 $(u,v)(1\leq u,v\leq 2n)$ 使得在其中一种安排方式中花 $u$ 和花 $v$ 颜色相同而在另一种安排方式中颜色不同。 Translated By Karry5307 ### 输入格式 一行一个~~孤独的~~正整数 $n(3\leq n\leq 5\times 10^4)$，意义见题目描述。 ### 输出格式 一行一个整数，代表所有可能的安排方式的美感之和，对 $998244353$ 取模。 ### 样例解释 当 $n=3$ 的时候，以下六种安排方式都有 $2\times 2=4$ 的美感  但是别的，比如说下图中左边那一种，美感为 $0$。右边的那一种不合法，因为它不对称。

题目描述

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 $ 2n $ flowers, numbered from $ 1 $ to $ 2n $ 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 $ 998244353 $ . Two arrangements are considered different, if a pair $ (u,v) $ ( $ 1<=u,v<=2n $ ) exists such that flowers $ u $ and $ v $ are of the same colour in one of them, but not in the other.

输入输出格式

输入格式

The first and only line of input contains a lonely positive integer $ n $ ( $ 3<=n<=50000 $ ) — the number of colours present on the Floral Clock.

输出格式

Output one integer — the sum of beauty over all possible arrangements of flowers, modulo $ 998244353 $ .

输入输出样例

输入样例 #1

3

输出样例 #1

24

输入样例 #2

4

输出样例 #2

4

输入样例 #3

7

输出样例 #3

1316

输入样例 #4

15

输出样例 #4

3436404

说明

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.