Treehouse Stairs

Problem Source

AHOI 2012

Problem Description

During the summer holiday, Xiaolong signed up for a mock wilderness survival training class to get fit. On the first night of training, the instructor gave them a tough problem. Because camping on the damp ground is unhealthy, they must camp in a treehouse up high. Xiaolong's treehouse is built on a tree of height $N+1$ chi ($N$ is a positive integer). Just as he was worrying about how to climb up, he noticed a pile of hollow square steel tubes nearby. After observing and measuring, he found that these tubes have different widths and heights in cross-section, but all are integer multiples of $1$ chi. The instructor ordered each team member to pick $N$ hollow tubes to build a staircase of total height $N$ chi leading up to the treehouse. Each step of the staircase is $1$ chi high and $1$ chi wide. If the tubes come in all sizes and each size is available in unlimited quantity, in how many ways can Xiaolong build the staircase?

For example, with a treehouse height of $4$ chi and a staircase height $N = 3$ chi, Xiaolong has the $5$ ways of building it shown in the figure:

Input Format

One positive integer $N$ ($1 \le N \le 500$), the height of the staircase.

Output Format

One positive integer: the number of ways to build it. (Note: the number of ways may be very large.)

Sample Input

3

Sample Output

5

Hint

For $100\%$ of the data, $1 \le N \le 500$.