Description

Xiaohu has just started kindergarten. The teacher gave him homework: first draw $3$ rows of cells. The first row has $3$ cells, the second row has $2$ cells, and the third row has $1$ cell. In each row, pieces can be placed from left to right, but except for the first row, the number of pieces placed in each row cannot exceed the number of pieces in the previous row. The number of pieces in the first row cannot be $0$, but the remaining rows may be empty. After playing for a while, Xiaohu said to his older brother Dahu: “There are many ways to place the pieces for this homework. I want to find them, but I do not know how many arrangements there are. Can you help me?”

Dahu is in the school’s informatics training team, and he immediately thought of using a computer to solve this problem. He quickly got the answer: $13$.

The next day, he brought the problem to school and asked: what if the first row has $N$ cells, the second row has $N-1$ cells, …, and the $N$-th row has $1$ cell? Now please help him solve this difficult problem.

Input Format

Only one line: a positive integer $N$.

Output Format

One line: the total number of arrangements.

2

4

3

13

Hint

Explanation for Sample 1: when $N=2$, there are the following $4$ ways to place pieces (* represents a piece, _ represents an empty cell): | Arrangement | 1 | 2 | 3 | 4 | | :----------- | :----------- | :----------- | :----------- | :----------- | | First row | *_ | ** | *_ | ** | | Second row | _ | _ | * | * |

Constraints:

For $30\%$ of the testdata: $1\le N\le 12$.

For $50\%$ of the testdata: $1\le N\le 30$.

For $100\%$ of the testdata: $1\le N\le 100$.

Translated by ChatGPT 5