#描述#
在n*n的方格棋盘上放置n 个车(可以攻击所在行、列)，求使它们不能互相攻击的方案总数。结果取模2^32。

#格式#
##输入格式##
输入包含多组数据，每组数据包含一个整数n(1&lt=n&lt=10^9)，处理到文件结束。

##输出格式##
每个输入对应一行输出结果。

#样例1#
##样例输入1##

2
3

##样例输出1##

2
6

#限制#
1000ms
32768KB

#提示#

#来源#
zjut_DD