[AHOI2012] 树屋阶梯

题目描述

![](https://cdn.luogu.com.cn/upload/pic/1630.png) ![](https://cdn.luogu.com.cn/upload/pic/1631.png)

输入输出格式

输入格式


一个正整数 $N$，表示阶梯的高度。

输出格式


一个正整数，表示搭建方法的个数。**注**：搭建方法的个数可能很大。

输入输出样例

输入样例 #1

3

输出样例 #1

5

说明

- 对于 $40\%$ 的数据，满足 $1\le N\le 20$。 - 对于 $80\%$ 的数据，满足 $1\le N\le 300$。 - 对于 $100\%$ 的数据，满足 $1\le N\le 500$。