红萌馆为了防备敌人的入侵,决定安装一个巨型防御塔。该防御塔拥有攻击高,范围广的特点。
但是防御塔的搭建也是非常复杂的,它一共由n个部件构成(每个部件互不相同)。方便起见,给每个部件都标上一个1到n的数字。
Izayoi Sakuya花费了数天时间从各种渠道获得了这n个部件,并把它们放在地上排成一个序列p(即p为n的排列)。
为了防止在搭建防御塔过程中因找部件而浪费了大量的时间,所以Izayoi Sakuya想要对这个序列进行排序,使得最终序列p = {1, 2, ...,n}。
由于条件的限制,所以每次只能选择任意两个部件进行交换(即选择i和j,交换pi 和 pj)。设K为最小的交换次数。
现在Izayoi Sakuya还不知道排列p为多少(因为还没来得及去统计),但是她想提前知道自己的工作量大概为多少(即K的期望)。
你能帮帮她吗?最终答案为 E(K) * n! module (109 + 7)。
注意:对于任意一个p,它出现的概率都是相同的(都为 1 / n!)。
输入数据包含多组数据,以EOF为结尾。
每组数据仅包含一行,且只有一个整数n。
0 < n ≤ 100,000
对于每组数据,输出Case #x: y,x为当前的数据组数(x是从1开始),y为答案。
1
2
3
Case #1: 0
Case #2: 1
Case #3: 7