Description

To make contestants pay attention to regular school subjects, Cirno специально added a math exercise from teacher Kamishirasawa Keine:

Find the number of ways to partition a set $\texttt{U}=\{1,2,3,\cdots,n\}$ into two subsets $S,T$ such that $|S|\notin S,|T|\notin T$.

Since the contestants cannot do big-integer arithmetic, you only need to output the answer modulo $998244353$.

Input Format

One line with one integer $n$.

Output Format

One line with one integer, representing the answer.

3

2

6

10

65535

459810767

Hint

Sample Explanation.

#1: Two valid partition schemes are $\{1,3\},\{2\}$ and $\{2\},\{1,3\}$.

Constraints.

For $100\%$ of the testdata, it is guaranteed that $1 \le n \le 10^5$.

Reprinted from XDUCPC 2021 online contest problem B.

Translated by ChatGPT 5