该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

三千世界鸦杀尽，此夜月明与君永不诀别！

题目描述

给定一个长度为$n-1$的序列

请你序列中的位置填入$0\sim n-2$，使得$\sum_{1\leq l\leq r<n}mex\{a_l,a_{l+1},…,a_{r-1},a_r\}$最大

其中$mex$是指没有出现在序列中的最小自然数。

例如：$mex\{1,2,3\}=0,mex\{0,1,4\}=2$

输入格式

输入一个数$n$

输出格式

答案对$998244353$取模。

样例 #1

样例输入 #1

3

样例输出 #1

3

样例 #2

样例输入 #2

5

样例输出 #2

13

提示

对于$n=3$，最佳策略是$0,1$

$mex\{0\}=1,mex\{1\}=0,mex\{0,1\}=2$

答案是$1+0+2=3$

$50\%$的数据：$n\leq 2000$

另外$30\%$的数据：$n\leq 2*10^6$

$100\%$的数据：$n\leq 2*10^9$