public static int count = 0;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
nQueen(new boolean[n][n], 0, 0, 0, n);
System.out.println(count);
}
public static void nQueen(boolean[][] board, int row, int col, int qpsf, int tq) {
if (qpsf == tq) {
++count;
return;
}
if (col == board[0].length) {
row++;
col = 0;
}
// negative base case
if (row == board.length) {
return;
}
if (isItSafeToPlaceTheQueen(board, row, col)) {
// Placed only if it is safe
board[row][col] = true;
nQueen(board, row + 1, 0,qpsf + 1, tq);
board[row][col] = false;
}
// not placed
nQueen(board, row, col + 1,qpsf, tq);
}
public static boolean isItSafeToPlaceTheQueen(boolean[][] board, int row, int col) {
// vertically upward
int r = row - 1;
int c = col;
while (r >= 0) {
if (board[r][c]) {
return false;
}
r--;
}
// horizontally left
r = row;
c = c - 1;
while (c >= 0) {
if (board[r][c]) {
return false;
}
c--;
}
// diagonally left
r = row - 1;
c = col - 1;
while (r >= 0 && c >= 0) {
if (board[r][c]) {
return false;
}
r--;
c--;
}
// diagonally right
r = row - 1;
c = col + 1;
while (r >= 0 && c < board[0].length) {
if (board[r][c]) {
return false;
}
r--;
c++;
}
return true;
}