正整数分解

题目描述

一个正整数n可以被分解为许多正整数的和，现请你编写程序通过递归方法求解一个正整数有多少种不同（例如对3进行分解得到1+2和2+1为同一种情况）的方法进行分解。

注意：该正整数自身也是一种可行的分解方案，例如2的分解方法包括1+1和2两种。

输入

输入数据包含一行，包含一个正整数n，为被分解的正整数。

输出

输出数据包含一行，包含一个整数，为总分解方法数。

输入样例

5

输出样例

7

样例解释

5的分解方案如下：

5=1+1+1+1+1

5=1+1+1+2

5=1+2+2

5=1+1+3

5=2+3

5=1+4

5=5

共7种。