Cut the gold bar
题号:NC220709
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

有一天,fishfloss被一阵暴风卷到了一个不知名的岛上,这个岛很漂亮,他想要好好参观一下,
但是他并不认路,很巧的是,在路途中他遇到了一个身无分文的人前来求助,于是他决定请这个人来当自己的导游。
fishfloss身上只有一把小刀和一根长度未知的金条,他每天给这个人长度为1的金条作为报酬,
在必须切n刀的情况下,金条有多少种可满足上述付款方式且能付完的长度?

输入描述:

一行,为切的刀数n 
(1≤n≤40)

输出描述:

一行,为金条有多少种长度
示例1

输入

复制
1

输出

复制
2

说明

切一刀的情况下,显然有2,3两种长度满足每天付1节金条题意。长度为2切1刀,成两个长度为1的,每天付给导游1,付两天。长度为3,切1刀分为1和2长度,第一天付1节金条,第二天付2节找回1节金条,第三天付3节金条,共付三天。
示例2

输入

复制
2

输出

复制
5

备注:

由于并非使用电子货币,所以这个导游不仅可以收钱,也可以找钱
但是不可以赊账!也不可以预支!