Roads in the Kingdom

In a certain kingdom, there are N cities. To enable residents to travel throughout the country, the cities need to be connected by roads in such a way that any resident can travel from one city to any other city.

However, according to the kingdom's primary law, the roads are demolished and reconstructed every year. Each year's road configuration must be unique and cannot replicate any previous configuration.

Legend has it that if the kingdom ever fails to create a new road configuration, it will be conquered. Your task is to determine how many years the kingdom can continue before this happens.

Input

A single integer - the number of cities N (1 ≤ N ≤ 75)

Output

The output should be the number of years the kingdom will last.

Examples