幼稚园大班的小梽同学在完成一个简单科学小实验，制造类似于“奇异夸克团”的物质。 奇异夸克团是一种理论上存在的物质，这种物质有一种同化的特性（链式反应），当奇异夸克团与其他物质接触时会将其同化为和自己一样的奇异夸克团。 随着实验的进行，小梽同学将“类奇异夸克团”的物质制造了出来，取名为z物质。这种z物质的特性为：只会同化二维平面中x轴方向和y轴方向的物质。 ps:被同化后的物质不具有同化特性。 例如：

在上方5*5的二维平面中z物质只会同化y轴方向的3，8，18，23。和x轴方向的11，12，14，15。

真正的题目： 制造出z物质的小梽同学，不禁陷入了思考。若将n*n的二维平面都给同化了，至少需n个z物质。那么有多少种放置方法呢？ 例如：

为一种

为另一种

输入

输入一个整数n,表示n*n的二维平面（1<=n<=100）

输出

n个z物质在n*n的二维平面中的放置方法数,(方法数大于1)

9

362880