> //能解开所有盒子的情况分为两类：
> //A>   用盒子1里的钥匙去开它对应的锁a_1,再用盒子a_1里的钥匙去开它对应的锁a_2，等等，依次类推。其中某一个a_s恰好是2号盒子
> //这样一来就构成了一个环：1-> a_1 -> a_2 -> .. -> a_s-1 -> a_s=2 -> a_s+1 -> .. -> a_n-1
> //也即，事实上只需一把钥匙就能打开所有的锁。此时盒子里放钥匙的方案就是(n-1)!种（后面n-1个位置由2到n进行全排列）
> 
> //B>   必须用两把钥匙才能打开所有的盒子，也即，每把钥匙能打开的锁各自构成了一个环，共两个环；
> //设两个环的大小分别为x和y，则有x+y=n。每组解对应的放置方案可以写为两条链:
> //1 -> a1 -> a2 -> .. -> a(x-1)  ,  2 -> b1 -> b2 -> .. -> b(y-1)
> //前一条链表示盒子1放a1, 盒子a2放a3, .. ,盒子a(x-1)放1,在a1,a2,..,a(x-1)取定后共(x-1)!种可能;
> //后一条链同理,在b1,b2,..,b(y-1)取定后共(y-1)!种可能
> //故可分为两条链的放置方案总数为：
> //Sigma( C(n-2, x-1)*(x-1)!*(y-1)! )
> //(Sigma是对x+y=n且x,y均为正整数求和，前面乘一个组合数是选定哪些数在链1、哪些数在链2上)
> //对此式求和后可知化简后为(n-1)!
> 
> //由加法原理知，总的方案数为：(n-1)! + (n-1)! = 2(n-1)!
> 
> #include <stdio.h>
> #define MAXN 205
> #define MAXM 1050
> #define BASE 10000
> int res[MAXN][MAXM]={0},msb[MAXN]={0}; //2*(i-1)!保存在res[i][]中，msb[i]为2*(i-1)!最高位的位置
> 
> int main(){
> 	int n,i,j;
> 	res[3][0]=4;
> 	msb[3]=0;
> 	for (i=3; i<MAXN-2; ++i){
> 		for (j=0; j<=msb[i]; ++j){
> 			res[i+1][j] += res[i][j]*i;
> 			res[i+1][j+1] += res[i+1][j]/BASE;
> 			res[i+1][j] %= BASE;
> 		}
> 		if (res[i+1][msb[i]+1])		msb[i+1]=msb[i]+1;
> 		else	msb[i+1]=msb[i];
> 	}
> 
> 	while (scanf("%d", &n)!=EOF && n!=-1){
> 		printf("N=%d:\n%d", n, res[n][msb[n]]);
> 		for (i=msb[n]-1; i>=0; --i)
> 			printf("%04d", res[n][i]);
> 		printf("\n");
> 	}
> 
> 	return 0;
> }