Đếm số cách đặt ~n~ quân hậu trên bàn cờ kích thước ~n \times n~ sao cho không có hai quân hậu nào tấn công nhau.

Hai quân hậu tấn công 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.

Một cách đặt ~5~ quân hậu hợp lệ:

X....
...X.
.X...
....X
..X..

Dữ liệu vào

Một dòng duy nhất chứa số nguyên ~n~.

Kết quả

In ra số cách đặt ~n~ quân hậu thỏa mãn.

Ví dụ

Đầu vào:

5

Đầu ra:

10

Giải thích: Với bàn cờ ~5 \times 5~ có đúng ~10~ cách đặt ~5~ quân hậu không tấn công nhau.

Giới hạn

• ~1 \le n \le 10~

Lưu ý rằng với ~n = 2~ và ~n = 3~ không có cách đặt nào, nên kết quả là ~0~.