#P18148. I Love Marathon Contest

I Love Marathon Contest

I Love Marathon Contest

圆形池塘岸边等距标有1到2N号位置,编号按顺时针增加。共有2N名互不相同的参赛者,其中N人戴红帽,另外N人戴白帽。

每个位置站一名参赛者,比赛按以下规则进行:

  • 位置1的参赛者拿到接力棒,开始顺时针跑。
  • 第i名跑者(1≤i≤2N−1)跑到仍在池塘边、且帽子颜色与自己不同的第一名参赛者处,把棒交给对方后离开池塘;接到棒的人继续按同样规则跑。
  • 第2N名跑者跑回位置1,结束比赛。

池塘一圈长度为1,所有跑者的总路程恰好是整数L。共有(2N)!种人员站位,请求出这些站位的L之和,对998244353取模。

输入格式

输入一个整数N,1≤N≤1000000。

输出格式

输出一个整数,表示所求总和模998244353的结果。

样例 1

1
2

样例 2

2
40

样例 3

3
1656

样例 4

4
112896

样例 5

5
11750400

说明

N=1时,两种人员站位的L均为1,总和为2。

N=2时,有六种颜色模式,其中交替颜色的两种模式L=1,其余四种L=2。每种颜色模式对应2!×2!=4种人员站位,总和为(2×1+4×2)×4=40。