← 返回题目列表

AtCoder · utpc2023_i

I. 我爱马拉松大赛

中文机器翻译题面 查看原题

配点 : 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