Bài toán xếp \(N\) quân hậu trên bàn cờ \(N imes N\) sao cho không có hai quân hậu nào tấn công lẫn nhau. Đếm số cách xếp hợp lệ.

Định dạng đầu vào

• Một dòng duy nhất chứa số nguyên dương \(N\) (\(1 \le N $\le 14\)).

Định dạng đầu ra

• In ra số lượng cách xếp hợp lệ.

Ví dụ

Input:

4

Output:

2

Giải thích: Với \(N=4\), có đúng 2 cấu hình xếp quân hậu hợp lệ.

Ràng buộc & Subtasks