解题思路

把问题看成把正整数 $n$ 划分成若干个正整数的有序序列。设 dp[s] 表示“按顺序凑成和为 s 的方案数”。最后一枚硬币面额取 x (1 ≤ x ≤ s)，前面部分就必须凑成 s-x，于是有转移：

边界为 dp[0] = 1（和为 0 的空序列仅 1 种）。依次从小到大计算 s = 1..n 即可。

题面描述

给定一个正整数 $n$。你拥有面额为 $1,2,3,\ldots,10^9$ 的硬币，每种面额的硬币数量都无限。求有多少种方式使所选硬币的总面额恰好为 $n$。 注意： 选择的顺序不同视为不同方案（例如 $2,1$ 与 $1,2$ 记为两种）。

输入输出

输入： 一行一个整数 $n$。

输出： 一行输出一个整数，表示组成面额 $n$ 的方案数。

数据范围

• $1 \le n \le 63$

样例

输入

2

输出

2

说明 可行方案：1,1；2。

输入

3

输出

4

说明 可行方案：1,1,1；2,1；1,2；3。