Description

Original source: AHOI 2012

During summer vacation, Xiaolong enrolled in a simulated wilderness survival training camp to improve his physical fitness. On the first night of training, the instructor presented them with a challenging problem. Due to the dampness of camping on the ground, they had to choose to camp in a treehouse at a higher elevation. The treehouse assigned to Xiaolong was built on a large tree with a height of $N+1$ feet. Just as he was worrying about how to climb up, he noticed a pile of hollow square steel materials nearby (as shown in Figure 1.1). After observation and measurement, he found that the width and height of these steel materials varied but were all integer multiples of $1$ foot. The instructor ordered each team member to select $N$ hollow steel materials to construct a staircase with a total height of $N$ feet to access the treehouse. Each step of the staircase must have a height of $1$ foot and a width of $1$ foot. Given that these steel materials come in various sizes and each size is available in sufficient quantities, how many different methods can Xiaolong use to build the staircase?

Note: To avoid stepping into empty space at night, the hollow side of the steel materials must absolutely not face upward.

Input Format

A positive integer $N$, representing the height of the staircase.

Output Format

A positive integer, representing the number of construction methods.

Note: The number of construction methods may be very large.

Sample 1

The following diagram shows $5$ construction methods:

3

5

Constraints and Hints

For all test cases, $1\le N\le 500$.