背景

:::epigraph "你见识到这世界的厉害了吧？"

"我见识到我自己的厉害了！" :::

题目描述

在解开了小移和小换之间的心结之后，你又解决了好多好多的排列计数问题。

这些问题的形式形形色色，有的将简直八竿子打不着的信息结合到了一起，有的含有错综复杂的大小关系让人毫无头绪，有的源于经典问题却被不起眼的额外限制破坏掉了美好的性质，还有些看似结构简单却有着严苛以至于遥不可及的复杂度要求。它们之中有大眼观察题、有大分讨题、有 dp 题、还有容斥题、双射题、生成函数题、分治 NTT 题、整式递推题、拉格朗日反演题、格路计数题、杨表题、群论题，还有包括多重要素而无法分类的请输入文本题。尽管记忆已经遥远，你依然记得最初遇到这些题时的震撼，这有时似乎比最终解决问题时的感受来得还要更清晰。你帮助小 S 解释了使冒泡排序次数取下界的排列的分布、帮小 K 找到了让大家始终舒适的毕业旅行方案、找回了如意因为意外而失去的目标、发现了藏于起落与循环中的讲不完的故事、算出了当年的纸条上「套路」与「智力」的交汇处所蕴藏的可能性、回答了赫尔德在「心动」背后和「潮水」面前的疑惑……随着你解开了越来越多的问题，你的事迹传遍了每条大街小巷，人们都羡慕你的热情和能力，纷纷将自己无法解决的排列计数题求助于你，你成了远近闻名的排列计数大师——

——总之，那些起伏不定而紧张刺激的日子已经过去了，今天也是平常的一天。

记 $f(n,m)$（$3\le m\le n$）表示满足如下性质的数列 $P_1,P_2,\cdots,P_m$ 的数量：

• $P_1,P_2,\cdots,P_m$ 两两不同且都属于集合 $\{1,2,\cdots,n\}$；
• 对于任意的 $i$（$3\le i\le m$)，满足 $[P_i<P_{i-1}]\ne[P_i<P_{i-2}]$。

其中，$[X]$ 的值在命题 $X$ 成立时为 $1$，反之为 $0$。

给定 $n$，求 $\sum_{i=3}^n f(n,i)$ 对 $998244353$ 取模的结果。

请注意，对于两个长度为 $m$ 的数列 $P_1,P_2,\cdots,P_m$ 和 $P'_1,P'_2,\cdots,P'_m$，被视为两个不同的数列，需要被统计两次，当且仅当存在 $i$（$1\le i\le m$）满足 $P_i\ne P'_i$。

输入格式

输入共一行，仅包含一个整数 $n$（$3\le n\le 10^6$）。

输出格式

输出共一行，仅包含一个整数，表示答案对 $998244353$ 取模的结果。

5

32