import java.io.*;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

public class Main {

    private static int[] curr;
    private static long solNr = 0;
    private static PrintWriter out;
    private static Set<Integer> mainDiag = new HashSet<Integer>(100), secDiag = new HashSet<Integer>(100);
    private static Set<Integer> row = new HashSet<Integer>(100);

    private static void solve(InputReader reader) {
        int n = reader.nextInt();
        curr = new int[n];

        back(0, n);
        out.println(solNr);
        out.flush();
    }

    private static void back(int pos, int n) {
        if (pos == n) {
            if (solNr == 0) {
                printSol();
            }

            solNr++;
        } else {

            for (int i = 0; i < n; i++) {
                curr[pos] = i;

                if (isValid(pos)) {
                    add(pos);
                    back(pos + 1, n);
                    remove(pos);
                }
            }
        }
    }

    private static void remove(int pos) {
        int main = mainNr(pos);
        int sec = secNr(pos);

        mainDiag.remove(main);
        secDiag.remove(sec);
        row.remove(curr[pos]);
    }

    private static void add(int pos) {
        int main = mainNr(pos);
        int sec = secNr(pos);

        mainDiag.add(main);
        secDiag.add(sec);
        row.add(curr[pos]);
    }

    private static int secNr(int pos) {
        return pos + curr[pos];
    }

    private static int mainNr(int pos) {
        return curr[pos] - pos;
    }

    private static boolean isValid(int pos) {
        int main = mainNr(pos);
        int sec = secNr(pos);

        return !row.contains(curr[pos]) && !mainDiag.contains(main) && !secDiag.contains(sec);
    }

    private static void printSol() {
        for (int i = 0; i < curr.length; i++) {
            out.print((curr[i]+1) + " ");
        }

        out.println();
    }

    public static void main(String[] args) throws FileNotFoundException {
        InputReader reader = new InputReader(new FileInputStream("damesah.in"));
        out = new PrintWriter(new FileOutputStream("damesah.out"));

        solve(reader);
    }

}


/**
 * Convenient and fast input reader.
 */

class InputReader {
    public BufferedReader reader;
    public StringTokenizer tokenizer;


    public InputReader(InputStream stream) {
        reader = new BufferedReader(new InputStreamReader(stream));
    }

    public String next() {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            try {
                tokenizer = new StringTokenizer(reader.readLine());
            } catch (IOException e) {
                throw new RuntimeException("FATAL ERROR", e);
            }
        }

        return tokenizer.nextToken();
    }

    public String nextLine() {
        try {
            return reader.readLine();
        } catch (IOException e) {
            throw new RuntimeException("ERROR", e);
        }
    }

    public int nextInt() {
        return Integer.valueOf(next());
    }

    public long nextLong() {
        return Long.valueOf(next());
    }
}