题目描述
空地上散发出光芒，汇成一个棋盘。整个棋盘共有n行n列，上面共有n枚棋子，棋子会不断变换位置，烛龙战队需要快速确定，在这个棋盘中，是否每行、每列有且仅有一个棋子，每条对角线上，最多有一个棋子。满足这些条件的棋子布局，被称为八皇后。
烛龙战队需要在这n*n的棋盘上摆下n枚棋子，形成八皇后的布局，最终要求出共有几种不同的摆放方式。
输入
输入包括两行。
第一行包含一个整数n，代表这是个n行n列的棋盘。（n< 15）
输出
输出包括一行，包含一个整数，代表共有n种不同的摆放方式。
样例输入
6样例输出
4