Sgu385 highlander

有一个由 $N$ 个人参与的游戏。游戏开始时，每个人都持有一张卡片，卡片上写着这 $N$ 个人中某个人的名字。

游戏开始前，从所有满足以下条件的卡片分配方案中等概率随机选择一种：

• 每个人恰好持有一张卡片；
• 每个人的名字恰好出现在一张卡片上；
• 没有人持有写着自己名字的卡片。

游戏开始后，每个人都会追逐自己所持卡片上写着的人。当 $A$ 追上 $B$ 后，$B$ 退出游戏，$A$ 获得 $B$ 当前持有的全部卡片。追逐发生的先后顺序可以任意。

当所有仍在游戏中的人都没有可以追逐的目标时，游戏结束。最终持有卡片数量最多的人为胜者；如果有多人并列持有最多的卡片，则他们均为胜者。

对于一个固定的初始分配方案，如果存在一种合法的追逐顺序，能够使某人成为胜者，则称此人为该分配方案的潜在胜者。

求潜在胜者人数关于初始随机分配方案的数学期望。

等价地，将每个人指向其初始卡片上所写的人，则初始分配形成一个没有自环的排列。潜在胜者恰好是所有最长环中的人。

输入格式

输入一个整数 $N$，表示参与游戏的人数。

输出格式

输出潜在胜者人数的数学期望。

答案与标准答案的绝对误差不超过 $10^{-9}$。

样例输入

2

样例输出

2.00000000000000000000

数据范围

• $2\le N\le 100$；
• 输出答案与标准答案的绝对误差不超过 $10^{-9}$。

来源与许可

本题题面与测试数据整理自 BZOJ。

样例 1

输入

2

输出

2.00000000000000000000