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

public class Main {

    private static int[] curr;
    private static long solNr = 0;
    private static PrintWriter out;

    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)) {
                    back(pos + 1, n);
                }
            }

        }
    }

    private static boolean isValid(int pos) {

        for (int i = 0; i < pos; i++) {
            if (curr[pos] == curr[i] || Math.abs(pos - i) == Math.abs(curr[pos] - curr[i])) {
                return false;
            }
        }

        return true;
    }

    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("dame.in"));
        out = new PrintWriter(new FileOutputStream("dame.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());
    }
}