Description

Input Format

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

Output Format

A positive integer, representing the number of ways to build it. Note: The number of ways may be very large.

3

5

Hint

• For $40\%$ of the testdata, $1 \le N \le 20$.
• For $80\%$ of the testdata, $1 \le N \le 300$.
• For $100\%$ of the testdata, $1 \le N \le 500$.

Translated by ChatGPT 5