import java.io.OutputStream;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.PrintWriter;
import java.io.FileInputStream;
import java.util.InputMismatchException;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream;
		try {
			inputStream = new FileInputStream("damesah.in");
		} catch (IOException e) {
			throw new RuntimeException(e);
		}
		OutputStream outputStream;
		try {
			outputStream = new FileOutputStream("damesah.out");
		} catch (IOException e) {
			throw new RuntimeException(e);
		}
		InputReader in = new InputReader(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		damesah solver = new damesah();
		solver.solve(1, in, out);
		out.close();
	}
}

class damesah {
    private int[] next, prev;
    private boolean[] diag1, diag2;
    private int N, sol;
    private boolean found;
    private int[] conf;

    PrintWriter out;

    public void solve(int testNumber, InputReader in, PrintWriter out) {
        N = in.nextInt();
        next = new int[N + 2];
        prev = new int[N + 2];
        diag1 = new boolean[3 * N + 1];
        diag2 = new boolean[3 * N + 1];

        for (int i = 1; i <= N; ++i) {
            prev[i] = i - 1;
            next[i] = i + 1;
        }
        next[0] = 1;
        prev[N + 1] = N;

        found = false;
        conf = new int[N + 1];
        sol = 0;
        this.out = out;
        back(1);
        out.println(sol);
    }

    private void back(int k) {
        if (k == N + 1) {
            ++sol;
            if (sol == 1) {
                for (int i = 1; i <= N; ++i)
                    out.print("" + conf[i] + ' ');
                out.println();
            }
        }

        for (int i = next[0]; i < N + 1; i = next[i]) {
            if (!diag1[k + i] && !diag2[k - i + N]) {
                diag1[k + i] = true;
                diag2[k - i + N] = true;
                next[prev[i]] = next[i];
                prev[next[i]] = prev[i];
                conf[k] = i;
                back(k + 1);
                diag1[k + i] = false;
                diag2[k - i + N] = false;
                next[prev[i]] = i;
                prev[next[i]] = i;
            }
        }
    }
}

class InputReader {
    private InputStream stream;
    private byte[] buf = new byte[1024];
    private int curChar;
    private int numChars;

    public InputReader(InputStream stream) {
        this.stream = stream;
    }

    public int read() {
        if (numChars == -1)
            throw new InputMismatchException();
        if (curChar >= numChars) {
            curChar = 0;
            try {
                numChars = stream.read(buf);
            } catch (IOException e) {
                throw new InputMismatchException();
            }
            if (numChars <= 0)
                return -1;
        }
        return buf[curChar++];
    }

    public int nextInt() {
        return Integer.parseInt(nextString());
    }

    public String nextString() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        StringBuffer res = new StringBuffer();
        do {
            res.appendCodePoint(c);
            c = read();
        } while (!isSpaceChar(c));

        return res.toString();
    }

    private boolean isSpaceChar(int c) {
        return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
    }

}