防御塔的搭建

题目描述

红萌馆为了防备敌人的入侵，决定安装一个巨型防御塔。该防御塔拥有攻击高，范围广的特点。
但是防御塔的搭建也是非常复杂的，它一共由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