Graph Game

Time limit2sMemory limit1024 MB

Summary

Count the number of distinct directed graphs on n labeled vertices that can arise as positions in a game where each move adds an edge without creating a cycle.

Level: Hard9 of 10
Topics: Combinatorics, Dynamic programming, Math, Graph
Solved: No attempts yet

Problem

Petya and Vasya play another interesting game. They have a sheet of paper with $n$ circles drawn on it, labeled with the numbers from $1$ to $n$ . The players take turns drawing arrows that connect circles. An arrow from circle $a$ to circle $b$ may be drawn if two conditions hold:

there is no arrow from $a$ to $b$ yet;
one cannot reach $a$ from $b$ by following arrows.

For example, in the position in Figure 1 one can draw one of three arrows (Figure 2).



Figure 1	Figure 2

The player who cannot make a move loses.

Petya decided to write a program that plays this game. To do so, he first wants to count how many different positions can appear on the board.

Input

The input file contains a single number $n$ ( $1\le n\le 100$ ).

Output

Output to the output file the number of possible positions, without leading zeros.

Notes

Here are all 25 possible positions for the example from the statement:

Examples1

Example 1
Input
```
3
```
Expected output
```
25
```