Problem Statement

Given a positive integer N, find the number, modulo 998244353, of subsets S of ${1, 2, \ldots, N$} that satisfy the following condition.

• Every positive integer at most N can be represented as the sum of some distinct elements of S, and there are at most two such representations.

Input

Input is given from Standard Input in the following format:
N

Output

Print the answer.

Constraints

• $1 \leq N \leq 1500$

Sample Input 1

3

Sample Output 1

2

The subsets {1,2} and {1,2,3} satisfy the condition.

Sample Input 2

5

Sample Output 2

5

Sample Input 3

1000

Sample Output 3

742952024

见题面 Input 部分

见题面 Output 部分