n皇后计数

题目描述

经典的 $n$ 皇后问题：在 $n \times n$ 棋盘上放 $n$ 个皇后使它们互不攻击。给定 $n$，输出解的个数。

输入格式

一行一个整数 $n$。

输出格式

一行一个整数，即解数。

数据范围