Absurdistan 的居民直到去年才学会如何修建道路。在这一发现之后，每个城市都决定修建一条通往其他某个城市的道路。每条新建的道路都可以双向通行。
Photo by Ivan McClellan
Absurdistan 充满了荒谬的巧合。所有 $N$ 个城市恰好用了一年时间完成了各自道路的修建。更令人惊讶的是，当道路完工时，人们发现可以通过新建的道路从任意一个城市到达其他任何城市。我们称这样的道路网络是连通的。出于对数学和概率的兴趣，你开始思考这种巧合究竟有多么不可思议。
任务
每个城市都从其他城市中均匀随机地选择一个城市并修建一条道路。计算该道路网络最终是连通的概率。
输入格式
第一行包含一个整数 $N$ ($2 \le N \le 140$)，表示城市的数量。
输出格式
输出一行，包含一个浮点数，表示由 $N$ 个城市和 $N$ 条道路组成的随机道路网络是连通的概率。你的答案绝对误差应不超过 $10^{-8}$。
样例
输入格式 1
4
输出格式 1
0.962962962963
输入格式 2
2
输出格式 2
1.000000000000