Absurdistan Roads II

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.

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

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.