Problem Description

Xiaohu has just started kindergarten. His teacher assigned him a homework task: first, draw 3 rows of grids, with the first row having 3 grids, the second row having 2 grids, and the third row having 1 grid. Chess pieces can be placed in the grids from left to right, but the number of chess pieces in each row, except the first one, must not exceed the number of chess pieces in the previous row. The first row must have at least one chess piece, but the subsequent rows can be empty. After playing with it for a while, Xiaohu told his older brother Dahua, "There are many ways to place the chess pieces, and I want to find out how many there are, but I don't know the answer. Can you help me?"

Dahua is a member of the school's informatics training team and immediately thought of using a computer to solve this problem. He quickly came up with the answer: 13.

The next day, he brought the problem to school and asked what if the first row had $N$ grids, the second row had $N-1$ grids, and so on, until the $N$-th row had 1 grid. Now, please help him solve this challenging problem.

Input Format

A single line containing a positive integer $N$.

Output Format

A single line containing the total number of placement schemes.

Sample Input and Output

Sample Input #1

2

Sample Output #1

4

Sample Input #2

3

Sample Output #2

13

Notes

For Sample 1, when $N=2$, there are 4 ways to place the chess pieces (* represents a chess piece, _ represents an empty grid):

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

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

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

见题面 Input 部分

见题面 Output 部分