Description

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

Input

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

Output

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

Sample

Input

2
3

Output

2
6

Source: zjut_DD