Description

N行N列的棋盘，放置N个皇后，要求每行、每列、每条对角线只能有1个皇后。求一共有多少种摆法

Format

Input

第1行：1个整数N（小于14）

Output

第1行：1个整数K，总的方案数。如果不能放，输出0.

Samples

4

2

Limitation

1s, 1024KiB for each test case.