import java.io.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) throws IOException {
        File file = new File("damesah.in");
        Scanner scanner = new Scanner(file);

        int n;
        n = scanner.nextInt();
        scanner.close();

        Chess_queen chq = new Chess_queen(n);
        chq.generate(0);

        FileWriter fileWriter = new FileWriter("damesah.out");
        PrintWriter printWriter = new PrintWriter(fileWriter);

        ArrayList<Integer> sol = chq.getFirstSolVec();
        for (int e : sol) printWriter.print((e + 1) + " ");
        printWriter.print("\n"+chq.getNumofSol());

        printWriter.close();
        fileWriter.close();
    }
}

class Chess_queen {
    public Chess_queen(int k) {
        n = k;
        row = new ArrayList<>(Collections.nCopies(n, 0));
        main_diag = new ArrayList<>(Collections.nCopies(2 * n , 0));
        anti_diag = new ArrayList<>(Collections.nCopies(2 * n , 0));
        col_pos = new ArrayList<>(Collections.nCopies(n, 0));
        foundsol = false;
        solnum = 0;
    }

    public void generate(int k) {
        for (int i = 0; i < n; i++) {
            if (row.get(i) == 0 && main_diag.get(i + k) == 0 && anti_diag.get(i - k + n) == 0) {
                main_diag.set(i + k, 1);
                anti_diag.set(i - k + n, 1);
                row.set(i, 1);

                col_pos.set(k, i);
                if (k != n - 1) generate(k + 1);
                else {
                    solnum++;
                    if (!foundsol) {
                        sol = new ArrayList<>(col_pos);
                        foundsol = true;
                    }
                }
                main_diag.set(i + k, 0);
                anti_diag.set(i - k + n, 0);
                row.set(i, 0);
            }
        }
    }

    public int getNumofSol() {
        return solnum;
    }

    public ArrayList<Integer> getFirstSolVec() {
        return sol;
    }

    private boolean foundsol;
    private ArrayList<Integer> sol;
    private ArrayList<Integer> col_pos;
    private ArrayList<Integer> row, main_diag, anti_diag;
    private int n, solnum;
}