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 boolean mainDiag[] = new boolean[100], secDiag[] = new boolean[100], row[] = new boolean[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[main] = false;
        secDiag[sec] = false;
        row[curr[pos]] = false;
    }

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

        mainDiag[main] = true;
        secDiag[sec] = true;
        row[curr[pos]] = true;
    }

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

    private static int mainNr(int pos) {
        return curr.length + 1 + curr[pos] - pos;
    }

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

        return !row[curr[pos]] && !mainDiag[main] && !secDiag[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());
    }
}