F - Counting Subsets Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 1200 点

問題文

正の整数 N が与えられるので，次の条件を満たす\{1,2,\ldots,N\} の部分集合 S の個数を 998244353 で割ったあまりを求めてください．

  • N 以下の正の整数はすべて S のいくつかの相異なる要素の和として表せる．さらに，そのような表し方は高々 2 通りである．

制約

  • 1 \leq N \leq 1500

入力

入力は以下の形式で標準入力から与えられる．

N

出力

答えを出力せよ．

入力例 1

3

出力例 1

2

\{1,2\} と \{1,2,3\} が条件を満たす部分集合です．

入力例 2

5

出力例 2

5

入力例 3

1000

出力例 3

742952024

Score : 1200 points

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.

Constraints

  • 1 \leq N \leq 1500

Input

Input is given from Standard Input in the following format:

N

Output

Print the answer.

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