[AHOI2012]树屋阶梯

题目描述

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

输入输出格式

输入格式


一个正整数N(1<=N<=500),表示阶梯的高度。

输出格式


一个正整数,表示搭建方法的个数。(注:搭建方法的个数可能很大)

输入输出样例

输入样例 #1

3

输出样例 #1

5

说明

40%的数据:1<=N<=20 80%的数据:1<=N<=300 100%的数据:1<=N<=500