import java.io.*;
import java.util.*;

public class Main {

    static int n, nrSol;
    static int pozDam[];
    static boolean colOcupate[], diagonalaSecOcupata[], diagonalaPrincOcupata[], ok=true;


    // READ
    static Scanner fin = new Scanner(System.in);
    public static void fileInput(String nameOfFile){
        //FILE INPUT
        try {
            fin = new Scanner(new File(nameOfFile));
            //ok = new Scanner(new File("Answers.txt"));
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }
    }
    public static void reading(){
        n = fin.nextInt();
        pozDam = new int[n];
        colOcupate = new boolean[n];
        diagonalaSecOcupata = new boolean[n*2];
        diagonalaPrincOcupata = new boolean[n*2];
    }

    // SOLVE
    public static void solve(int k){
        if (k==n) {
            if (ok){
                writing();
                ok = false;
            }
            nrSol++;
        }
        else
            for (int i = 0; i < n; i++){
                if (eligibil(k, i)){
                    ocupa(k, i, true);
                    solve(k+1);
                    ocupa(k, i, false);
                }
            }
    }

    public static void ocupa(int lin, int col, boolean valAdevar){
        colOcupate[col] = valAdevar;
        pozDam[lin] = col;
        diagonalaPrincOcupata[lin+col] = valAdevar;
        diagonalaSecOcupata[lin + n - col - 1] = valAdevar;
    }

    public static boolean eligibil(int lin, int col){
        if (colOcupate[col])
            return false;
        if (diagonalaPrincOcupata[lin+col] || diagonalaSecOcupata[lin + n - col - 1])
            return false;
        return true;
    }
    // WRITE
    static PrintStream out = null;

    public static void fileOutput(String nameOfFile){
        //FILE OUTPUT
        try {
            out = new PrintStream(new FileOutputStream(nameOfFile));
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }
        System.setOut(out);
    }
    public static void writing(){
        for (int i = 0; i < n; i++) {
            out.print(pozDam[i] + 1);
            out.print(" ");
        }
        out.println();
    }

    public static void main(String[] args) {
        fileInput("damesah.in");
        fileOutput("damesah.out");
        reading();
        solve(0);
        out.println(nrSol);
    }
}