class nqueens {
  public int sols = 0;
  private int[] colbad;
  private int[] diagbadleft, diagbadright;
  public nqueens(int width) {
    colbad = new int[width];
    diagbadleft = new int[width*2 - 1];
    diagbadright = new int[width*3];
  }

  public void placeQueen(int row, int qleft) {
    //if(qleft == 0 ) {
    if(qleft == 0) {
      //System.out.println(row + " " + colbad.length);
      sols++;
      return;
    }

    for(; row < colbad.length; row++) {
      for(int j = 0; j < colbad.length; j++) {
        if(!(colbad[j] == 1 || diagbadleft[row+j] == 1 || diagbadright[j-row+colbad.length] == 1)) {
          colbad[j] = 1;
          diagbadleft[row+j] = 1;
          diagbadright[j-row+colbad.length] = 1;
          placeQueen(row+1,qleft-1);
          diagbadleft[row+j] = 0;
          diagbadright[j-row+colbad.length] = 0;
          colbad[j] = 0;
        }
      }
    }
  }

  public static void main(String[] args) {
    int width = Integer.parseInt(args[0]);
    nqueens board = new nqueens(width);
    double start = System.currentTimeMillis();
    board.placeQueen(0,width);
    System.out.println(System.currentTimeMillis() - start);
    System.out.println(board.sols);
  }
}