Absurdistan Roads II

Time limit1sMemory limit256 MB

Summary

N cities each build a road to one random other city; compute the probability that the N roads connect all cities.

Level: Hard8 of 10
Topics: Combinatorics, Probability, Graph, Dynamic programming
Solved: No attempts yet

Problem

Absurdistan has $N$ cities. Last year every city picked one city other than itself and built a single road joining the two. Every road can be travelled in both directions.

Each city picks uniformly at random among the other $N-1$ cities, and the cities choose independently. So there are $(N-1)^N$ possible road networks and all of them are equally likely. If two cities pick each other, two separate roads run between them.

The road network is connected when the $N$ roads let you travel from any city to every other city. Compute the probability that the road network is connected.

Input

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

Output

Print the probability that the road network is connected. Print exactly 12 digits after the decimal point, rounding the 13th digit away from zero when it is 5 or more. If the probability is 1, print 1.000000000000.

Examples2

Example 1
Input
```
4
```
Expected output
```
0.962962962963
```
Example 2
Input
```
2
```
Expected output
```
1.000000000000
```