题目描述

在一个 N×N 的国际象棋棋盘上放置 N 个皇后，使得任意两个皇后都不能互相攻击。 皇后可以攻击同一行、同一列、同一两条斜线上的所有棋子。 请输出所有合法的摆放方案数。

输入描述

输入共1行，1个整数 N ，表示棋盘的大小。

输出描述

输出共1行，1个整数，表示方案数。

数据样例1

输入数据

4

输出数据

2

数据样例2

输入数据

8

输出数据

92