题目描述

在 $N * N$ 的方格棋盘放置了 $N$ 个皇后，使得它们不相互攻击（即任意 2 个皇后不允许处在同一排，同一列，也不允许处在与棋盘边框成 45 角的斜线上。 你的任务是，对于给定的 $N$，求出有多少种合法的放置方法。

输入格式

输入共一行，为一个正整数 $N(N≤16)$，表示棋盘和皇后的数量。

输出格式

共一行，为一个正整数，表示皇后的不同放置方案的数量。

样例

输入#1

8

输出#1

92