现有n种不同形状的宝石，每种 n 颗，共n²颗。同一种形状的n颗宝石分别具有n种不同的颜色c₁ ,c₂ ,…… ,c_n中的一种颜色。欲将这 n²颗宝石排列成n行n列的一个方阵，使方阵中每一行和每一列的宝石都有n种不同形状和n种不同颜色。试设计一个算法，计算出对于给定的n，有多少种不同的宝石排列方案。

输入数据为1 个正整数n，0<n<9。

将计算出的宝石排列方案数输出