花钟多年来一直伫立在镜湖畔。虽然无法留住时间,但却让人想起时光的流逝,想起往日的美好时光。
花钟的边缘有 2n 朵花,顺时针编号为 1 到 2n,每朵花在所有 n 种可能的颜色中都有一种颜色。对于每种颜色,恰好有两朵花,它们之间的距离要么小于或等于 2,要么等于 n。另外,如果u和v的花颜色相同,那么与u相对的花和与v相对的花也应该是相同的颜色——对称是美丽的!
正式来说,两朵花之间的距离是 1 加上它们之间的小弧(或半圆)上的花数。下面是 n = 6 的可能排列,涵盖了所有可能性。
布置的美感被定义为由所有相同颜色的相对花朵分隔的花段长度的乘积。换句话说,为了计算美度,我们从圆圈中删除所有与相对的花朵颜色相同的花朵。那么,美感就是所有剩余线段长度的乘积。请注意,我们在此产品中包含长度为 0 的段。如果没有与对面花颜色相同的花,则美度等于 0。例如,上述排列的美度等于 1 × 3 × 1 × 3 = 9 — 线段为 {2}、{4, 5, 6}、{8} 和 {10, 11, 12}。
在满足约束的同时,可能有很多不同的安排。找出所有可能排列的美度之和,以 998 244 353 为模。如果存在一对 (u, v) (1 ≤ u, v ≤ 2n) 且花 u 和 v 在其中一个中颜色相同,但在另一个中颜色不同,则两种排列被认为是不同的。
输入
输入的第一行也是唯一一行包含一个孤独的正整数 n (3 ≤ n ≤ 50 000) — 花钟上出现的颜色数量。
输出
输出一个整数——所有可能的花朵排列的美丽度之和,以 998 244 353 为模。
示例
输入 #1
3
输出 #1
24
输入 #2
4
输出 #2
4
输入 #3
7
输出 #3
1316
输入#4
15
输出#4
3436404
注意
当 n = 3 时,以下六种排列的美度均为 2 × 2 = 4。
而许多其他的,例如下图中左边的,美感为0。右边的则无效,因为它是不对称的。