题目描述

给定一个正整数 $N$，找到满足以下条件的子集 $S$ 的数量（取模 $998244353$）：

• 每个小于等于 $N$ 的正整数都可以表示为 $S$ 中一些不同元素的和，并且最多有两种这样的表示方法。

约束条件

• $1 \leq N \leq 1500$

输入

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

$N$

输出

输出答案。

示例 1

3

示例 1 输出

2

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

示例 2

5

示例 2 输出

5

示例 3

1000

示例 3 输出

742952024