测试数据来自 system/1687

背景

哇，眼前事一片一望无际的平原，回过神来。嘟嘟发现自己竟然来到了微观世界，太神奇了。仔细一瞧，眼前一个又一个的就是无处不在的微生物。原来细菌也是成群生活得啊，嘟嘟好奇的数起细菌的家族数。

描述

如果假设一个细菌群体有N家细菌，就可以把它们的底牌当做一个N*N的方阵，在这个方阵上第I列的第I 行都有一个病毒，它们不会居住在病毒上的，同时每行每列只能居住一家细菌。于是很快算出一个有N家细菌的细菌群体的居住地分布方法数。
这是病毒的一种排列方法:

格式

输入格式

一个整数N 代表细菌家数

输出格式

一个整数sum代表方法数

样例1

样例输入1

3

样例输出1

2

限制

各个测试点1s

提示

对于30%的数据，n <= 10
对于全部数据 n <= 1000