The county where the National Olympiad in Informatics is held this year it is a little bit strange. In the county there are N cities, numbered from 1 to N. Each of the N cities of the county is connected to exactly two other cities, through bidirectional roads. Even stranger is the fact that, inside this roads system it is not always possible to get from every town to any other town walking these roads. Anyway, the inhabitants of the county are very proud of their system and they think there is not another like this. You want to prove them the opposite and for this you want to calculate how many different road systems, with the upper feature, exist. Two systems are considered different if there is at least one road between a pair of cities i and j inside the first system, which does not exist inside the second one.

Write a program that calculates how many different road systems exist.

From the input, you will read the integer value n(3 <= n <= 100), representing the number of cities of the county.

In the output, you will write an integer value, representing the number of different street systems, with the feature that every city is connected through direct streets to exactly two other cities.

4

3