题目描述

在一个n×n的棋盘上放置n个国际象棋中的皇后，要求所有的皇后之间都不形成攻击（处在同一行或同一列或同一斜线上的皇后会互相攻击）。

请你给出所有可能的排布方案数。

输入格式

一个整数n

输出格式

一个整数表示方案数

样例数据

input

4

output

2

数据规模与约定

n<=8

时间限制：$1 \text {s}$

空间限制：$256 \text {MB}$