配点 : 100 点
問題文
在某个池塘举行马拉松比赛。池塘是圆形的,沿池塘外周顺时针以等间距标注了 1, 2,\ldots, 2N 标记。马拉松比赛的参与者有 2N 人,其中 N 有的人戴着红色的帽子,其余的 N 人戴着白色的帽子。
马拉松比赛如下进行。
- 2N 对于每一个标记,有正好 1 个人到达该位置。
- 印 1 处于标记位置的人握着接力棒,顺时针开始跑步。
- i 番目 (1 \le i \le 2N - 1) 跑向 的人会一直跑,直到到达最先拥有不同颜色帽子的人的位置。到达后,将接力棒交给对方并离开池塘。接到接力棒的人顺时针开始跑。
- 2N 第 跑的人会跑到标记 1 所在位置,结束马拉松比赛。
池 1 圈的长度为 1 以2N 人跑的总距离为整数,这个被称为 L 。
可能 2N 人的配置有 (2N)! 种情况,不过,对于所有这些情况 L 的总和 998244353 求以 的余数。
制約
- 所有输入均为整数
- 1 \leq N \leq 10^6
入力
输入是按以下格式从标准输入给出的。
N
出力
答案 请打印除以 1 行输出。
入力例 1
1
出力例 1
2
可能的排列有 2 种情况,但是无论哪种情况 L=1 。 对于
入力例 2
2
出力例 2
40
参与者戴的帽子颜色从标记 1 所在位置依次为
- 红红白白时 L=2
- 红白红白时 L=1
- 红白白红时 L=2
- 白红红白时 L=2
- 白红白红时 L=1
- 白白红红时 L=2
。每种情况下 4 种排列存在,因此对于所有可能的 24 种排列 L 的总和是 (2 + 1 + 2 + 2 + 1 + 2) \times 4 = 40 。
入力例 3
3
出力例 3
1656
入力例 4
4
出力例 4
112896
入力例 5
5
出力例 5
11750400