Migrated from Lutece 3220 子集和问题

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Tag: 转化，dp

给定正整数 $n$，求有多少 $\{1,2,\dots ,n\}$ 的子集 $S$ 满足任意一个 $1$ 到 $n$ 的整数都能被表示成 $S$ 的子集和，且方案数小于等于 $2$。

对 $998244353$ 取模。

Input

一行一个正整数 $n$。

Output

一行一个整数表示答案。

Samples

3

2

5

5

1000

742952024

Constraints

$1\le n\le 1500$

Resources

2024 UESTC ICPC Training for Math