题目描述

小明通过题目恢复字符串深刻的理解了kmp算法。

但是作为复读机的小明，决定再次解释一遍next数组的定义：

给定一个只包含小写字母的字符串$s$，下标从$1$开始编号，$next[i](next[i]<i)$表示的是最大的符合条件的位置，满足：$s_{[1,next[i]]}=s_{[i-next[i]+1,i]}$，如果不存在这样的数字，则$next[i]=0$。

例如，字符串$abcabcaa$，$next$数组为：$[0,0,0,1,2,3,4,1]$。

这次小明好奇的内容是，假设有一个长度为$n$的字符串，这个字符串的每一位可以是任意字符，那么，这个串的next数组有多少种呢？

输入格式

第一行输入$n$。

输出格式

输出一个数字表示答案$mod\ 998244353$。

样例输入 #1

1

样例输出 #1

1

样例输入 #2

2

样例输出 #2

2

样例解释 #2

显然只有$[0,0]$和$[0,1]$两种。

样例输入 #3

3

样例输出 #3

4

样例解释 #3

答案有$[0,0,0],[0,0,1],[0,1,0],[0,1,2]$四种。

这显然是出题人友好的提示，友情的赠予的友善的$5$分。

数据范围

对于100%的数据：$3\leq N\leq 22$。