题目描述

为了让选手们重视文化课，Cirno 特意加入了一道 Kamishirasawa Keine 老师的数学练习：

求将一个集合 $\texttt{U}=\{1,2,3,\cdots,n\}$ 划分成两个子集 $S,T$，使得 $|S|\notin S,|T|\notin T$ 的方案数。

$|S|$ 和 $|T|$ 分别指这两个集合的大小。

由于选手都不会高精度，所以答案只需要对 $998244353$ 取模即可。

输入格式

一行一个整数 $n$。

输出格式

一行，一个整数，表示答案。

3

2

6

10

65535

459810767

样例 1 解释

两种合法的划分方案为 $\{1,3\},\{2\}$ 与 $\{2\},\{1,3\}$ 。

数据范围

对于 $100\%$ 的数据，保证 $1 \le n \le 10^5$。