C1091 [Contest #6]permutation

内存限制:256 MB 时间限制:1000 ms

题目描述

(在分隔线以上没有关于题目的讯息)

「呐,小雪,那个比赛还在继续吧?」

「是的。败者对胜者要言听计从……」

对突如其来的话题雪之下疑惑地回答道。由比滨上前轻轻握住她的手臂,用明朗的声音正对她说道。

「现在小雪身上的问题,我已经知道答案了」

由比滨轻轻地抚摩着雪之下的衣袖。

雪之下伤脑筋的问题,在她的做过的行为和说过的话语中都有所体现。

更何况雪之下阳乃也曾明言过,她不知道对现在的雪之下雪乃该怎么办才好。她所说的具体是指哪方面呢。和母亲,和姐姐,以及和我们的关系。可能是其中之一,也可能是全部。

「我……」

雪之下的语气满是迷茫,她无力地垂下头,紧接而来的「不明白」三个字,小声到仿佛下一瞬间就要消散在风中。

「我想……那大概就是我们之间的答案」

结果,我和她都还是不懂。

如果理解了的话一定会开始崩坏,那样我们就会盖上盖子,假装自己看不到它慢慢腐坏的过程。所以,反正无论怎么做都会迎来结束,至少不要再失去任何东西了。

这就是我们现在行走的道路尽头会给予我们的结论。

由比滨短暂地中断话语,轻轻的摇摇头,随后再次真诚地直视我们。

「于是,所以……要是我赢了的话,我要收下全部。也许这样很狡猾……。但这是我能想到的唯一方法……。我希望我们一直都能保持现在这样」

所以由比滨先把这个答案,把这唯一的结论摆在了我们面前。不顾条件或假设或公式如何,她都选择了无视这一切。

她在说,无论我们再经历怎样的过程,遭遇怎样的状况,烦恼于不可能成立的等式,只有答案不能再改变。就像做梦一样,一直度过这开心的时光。

「你们觉得呢?」

团子究竟为什么要说出这样的话呢?这是她所喜欢的吗?

并不是,但是没有办法改变。永无止境的错误,遥不可及的答案。

也许,只有排列才是正确的吧。


一个长度为 $n$ 的排列是正确的,当且仅当它不存在非平凡(长度不为 $1$ 或 $n$)的连续子序列,使得它的值也是连续的(见注解)。例如 $[2413]$ 是正确的,但 $[132]$ 是不正确的 (因为 $[32]$ 为 $[132]$ 的一个非平凡子序列),$[7164532]$ 也是不正确的 (因为 [6453]、[64532]、[164532] 都是非平凡且值也连续的子序列)。

真物,又是什么呢?团子也不知道,但是她知道有多少长度为 $n$ 的正确的排列。你知道吗?

简要题意,求长度为 $n$ 的不存在非平凡连续子序列的排列数目。

注:一个序列是连续的,当且仅当把这个序列的值由小到大排序后,第 $i$ 个数的值是第 $1$ 个数的值加上 $i-1$。

输入格式

一行一个正整数 $n$($1\leq n \leq 10^5$),表示排列的长度。

输出

一行一个整数,表示长度为 $n$ 的正确的排列个数模 $998244353$ 的值。

样例

样例输入 1

4

样例输出 1

2

提示

在样例中,正确的排列有 $[2413]$,$[3142]$。