#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。