Đếm cách đặt N quân hậu

Cho bàn cờ kích thước \(N \times N\). Hãy đếm số cách đặt \(N\) quân hậu lên bàn cờ sao cho không có hai quân hậu nào ăn nhau. Hai quân hậu ăn nhau nếu chúng nằm trên cùng một hàng, cùng một cột hoặc cùng một đường chéo.

Hai cách đặt được coi là khác nhau nếu có một ô có quân hậu trong cách này nhưng không có trong cách kia (không coi các cách đối xứng hay xoay là giống nhau).

Input

• Một số nguyên \(N\) (\(1 \le N \le 13\)).

Output

• In số cách đặt.

Scoring

• Có \(50\%\) số test với \(N \le 8\).

Sample Input 1

4

Sample Output 1

2

Sample Input 2

6

Sample Output 2

4

Notes

Với \(N = 4\) có 2 cách: quân hậu ở hàng \(1, 2, 3, 4\) lần lượt đặt tại cột \((2, 4, 1, 3)\) hoặc \((3, 1, 4, 2)\).