题目描述

在 $n\times n$ 棋盘放置 $n$ 个皇后，使任意两个皇后不在同一行、列或对角线上。求方案数。

输入格式

一行一个整数 $n$。

输出格式

输出方案数。

样例

4

2

数据规模与约定

$1\le n\le13$。