Description

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

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

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

Input Format

一行一个整数 $n$。

Output Format

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

3

2

6

10

65535

459810767

Hint

样例解释

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

数据范围

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

重收录自 XDUCPC 2021 网络赛 B。