KTH Challenge 2015 Warm-up

#### Start

2015-04-21 23:00 CEST

## KTH Challenge 2015 Warm-up

#### End

2015-04-26 11:00 CEST
The end is near!
Contest is over.
Not yet started.
Contest is starting in -1155 days 14:33:26

108:00:00

#### Time remaining

0:00:00

Photo by Ivan McClellan

The people of Absurdistan discovered how to build roads only last year. After the discovery, each city decided to build its own road, connecting the city with some other city. Each newly built road can be used in both directions.

Absurdistan is full of absurd coincidences. It took all $N$ cities precisely one year to build their roads. And even more surprisingly, when the roads were finished it was possible to travel from every city to any other city using the newly built roads. We say that such a road network is connected. Being interested in mathematics and probability, you started wondering how unlikely this coincidence really is.

Each city picked uniformly at random another city to which they built a road. Calculate the probability that the road network ends up being connected.

## Input

The first line contains an integer $N$ $(2\le N\le 140)$ – the number of cities.

## Output

Output one line containing a floating point number denoting the probability that the randomly built road network with $N$ cities and $N$ roads is connected. Your answer should have an absolute error of at most $10^{-8}$.

Sample Input 1 Sample Output 1
4

0.962962962963

Sample Input 2 Sample Output 2
2

1.000000000000