题目描述

给定一个正整数 $N$，请计算满足以下条件的 $\{1,2,\ldots,N\}$ 的子集 $S$ 的个数，并将答案对 $998244353$ 取模后输出。

• 不超过 $N$ 的每一个正整数都可以表示为 $S$ 中若干个不同元素的和，并且每个数的表示方式最多只有 $2$ 种。

输入格式

输入从标准输入中给出，格式如下：

$N$

输出格式

请输出答案。

样例 1

输入

3

输出

2

样例 2

输入

5

输出

5

样例 3

输入

1000

输出

742952024

说明/提示

限制条件

• $1 \leq N \leq 1500$

样例解释 1

$\{1,2\}$ 和 $\{1,2,3\}$ 是满足条件的子集。

由 ChatGPT 4.1 翻译