← 返回题目列表

AtCoder · arc143_f

F. 计算子集

中文机器翻译题面 查看原题

分数: 1200 点

问题陈述

给定一个正整数 N,求模数 998244353,子集 S of \{1, 2, \ldots, N\} 满足以下条件。

  • 最多每个正整数 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