Playing with graph

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.



One integer n (1n100).


Print the number of possible positions without leading zeros.

Time limit 1 second
Memory limit 128 MiB
Input example #1
Output example #1
Source 2006, XIV St. Petersburg School Programming Team Championship, November 6, Problem D