问题描述

$N\times N$ 的棋盘上要求放置 $N$ 个皇后，要求不允许同一行或同一列或同一条斜线（45°）上有同一个皇后。

问可以放置全部皇后的方案数是多少？

输入格式

输入一行一个正整数 $N$。$(1\le N\le 10)$

输出格式

输出一个整数，表示方案数。

样例输入

5

样例输出

10