Bài toán N-Queens kinh điển: xếp \(N\) quân hậu lên bàn cờ \(N \times N\) sao cho không hai quân hậu nào ăn nhau.

Hai quân hậu ăn nhau nếu chúng cùng hàng, cùng cột, hoặc cùng đường chéo. Đếm số cách xếp thỏa mãn.

Gợi ý: Xếp từng hàng, dùng 3 mảng đánh dấu:

• col[c] — cột \(c\) đã có hậu
• diag1[i+c] — đường chéo chính
• diag2[i-c+N] — đường chéo phụ

Input

Một dòng duy nhất chứa số nguyên \(n\) (\(1 \le n \le 12\)).

Output

In ra số cách xếp \(n\) quân hậu thỏa mãn.

Example

8

Output:

92