[R9F]硬币问题 - 代码源竞赛平台

时空限制

1S/512M

题目描述

有 $n$ 种硬币，第 $i$ 种硬币的数量为 $i$，单个的价值也为 $i$。

从这些硬币中选出一些使得选中硬币的总价值恰好为 $n$，求有多少个不同方案，对 $998244353$ 取模。如果对于任意一种硬币，两个方案选中的数量不同，那么算作两种不同方案。

格式

输入格式

第一行包含一个整数 $n$，表示硬币的种类数。

输出格式

输出一个整数，表示选中硬币的总价值恰好为 $n$ 的方案的数量。对 $998244353$ 取模。

样例

样例输入 #1

9

样例输出 #1

13

样例解释 #1

总价值恰好为 $9$ 的不同方案有 $13$ 个：$9=9$、$9=8+1$、$9=7+2$、$9=6+3$、$9=6+2+1$、$9=5+4$、$9=5+3+1$、$9=5+2+2$、$9=4+4+1$、$9=4+3+2$、$9=4+2+2+1$、$9=3+3+3$、$9=3+3+2+1$。

样例输入 #2

199

样例输出 #2

949425260

样例输入 #3

1000

样例输出 #3

548519183

数据规模

对于 $20\%$ 的数据，$n\leq 200$。

对于 $60\%$ 的数据，$n\leq 5000$。

对于 $100\%$ 的数据，$1\leq n\leq 10^5$。