Playing with graph

Peter and Vasil are playing another good game. They have a sheet of paper, which shows the n circles labeled with numbers from 1 to n. Participants in turn draw arrows connecting the circles. In this case the arrow of a ring in a circle b allowed to hold if the following two conditions:

1. there are no arrows from a to b;

2. can not get the arrow from b to a.

For example, at the left position we can put one of three arrows (shown at the right).

The loser is one who can not make a move.

Peter decided to write a program that plays in this game. To do this, he wants to first count how many different positions can come on a sheet.

Here are all 25 items from the condition.

Input

One integer n (1 ≤ n ≤ 100).

Output

Print the number of possible positions without leading zeros.

Examples