Problem Background

"Cnoi2021" Cirno's Easy Round II Warm-up has begun.

Problem Description

To emphasize the importance of academic subjects, Cirno has included a mathematical exercise from Teacher Kamishirasawa Keine:

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

Since the contestants are not familiar with high precision, the answer should be taken modulo $998244353$.

Input Format

A single line containing an integer $n$.

Output Format

A single line containing an integer, representing the answer.

Sample Input and Output

Sample Input #1

3

Sample Output #1

2

Sample Input #2

6

Sample Output #2

10

Sample Input #3

65535

Sample Output #3

459810767

Notes

Sample Explanation

For #1: The two valid partitioning schemes are $\{1,3\},\{2\}$ and $\{2\},\{1,3\}$.

Data Range

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

见题面 Input 部分

见题面 Output 部分