Mô tả và yêu cầu

Như các bạn đã biết thì một quân hậu trên bàn cờ có thể di chuyển theo hàng ngang, cột dọc và 2 đường chéo.

Bài toán được đặt ra như sau: Cho một bàn cờ có kích thước NxN (N ≥ 1). Bạn có thể đặt đúng N quân hậu lên bàn cờ (mỗi ô chỉ chứa tối đa một quân hậu). Hãy đưa ra cách đặt N quân hậu sao cho không có 2 quân hậu nào ăn được nhau, nói cách khác là trên mỗi hàng, một cột, mỗi đường chéo của bàn cờ chỉ chứa tối đa một quân hậu.

Ví dụ với N = 4 thì có 2 cách đặt thỏa mãn như sau:

Dữ liệu vào

Vào từ thiết bị nhập chuẩn chứa số nguyên n là số quân hậu trên bàn cờ vua kích thước n x n.

Dữ liệu ra

Ghi ra file thiết bị xuất chuẩn chứa số nguyên là số các phương án tìm được.

Ví dụ

4

2