题目描述

转眼到了2008年的6月9日，盼望已久的高考结束了。我们踏上了向西的旅程（本来是想写西去之路，可是考虑不太妥当）。可可西里，多么诱人的名词，充满了奇幻的色彩和自然的淳朴。从可可西里徒步走回家的决定是

在$\red{1}$年半前定下的，而现在，终于可以实现那个钩过手指的预定。我们的可可西里。

在回家的路上，疯子和蚊子看到了许多可爱的藏羚羊，无意之中疯子和蚊子发现藏羚羊的居住地的分布也是有规律的，虽然疯子和蚊子早就听说藏羚羊是一种群体性很强又有超高$\red{IQ}$的动物，但是还是为它们的居住地分布规律感到惊叹。经过细心的观察，疯子和蚊子发现，如果假设一个藏羚羊群体有$\red{N}$只羊，就可以把它们的领地当做一个$\red{N×N}$的方阵，在这个方阵上第$\red{I}$列的第$\red{I}$ 行都有一个圣地，它们不会居住在圣地，同时每行每列只能居住一只羚羊。于是他们很快算出一个有$\red{N}$只羊的藏羚羊群体的居住地分布方法数。下表是圣地的一种排列方法

输入格式

一个整数$\red{N}$ 代表藏羚羊的个数

输出格式

一个整数$\red{sum}$代表方法数

样例

输入样例

4

输出样例

9

提示

对于$\red{30\%}$的数据，$\red{n≤0}$，对于全部数据$\red{n≤1000}$