import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;

public class Main {
	
	public static int n, counter;
	public static int[] v, lines, columns;
	public static char[][] queenTable;
	public static ArrayList<Integer> configuration;
	
	public static boolean checkDiagonals(int x, int y) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (queenTable[i][j] != '0') {
					if (i != x || j != y) {
						if (Math.abs(i-x) == Math.abs(j-y)) {
							return false;
						}
					}	
				}
			}
		}
		return true;
	}
	
	public static void bk(int k) {
		
		//New configuration found!
		if (k == n+1) {
			//Save first configuration
			if (configuration.size() == 0) {
				for (int i = 1; i <= n; i++) {
					for (int j = 1; j <= n; j++) {
						if (queenTable[i][j] != '0') {
							configuration.add(j);
						}
					}
				}
			}
			//Counter the possibilities.
			counter ++;
			return;
		}
		
		for (int i = 1; i <= n; i++) {
			
			//Try with another position(column)
			v[k]++;
			if (lines[v[k]] == 0 && columns[v[k]] == 0 && checkDiagonals(k, v[k])) {
					queenTable[k][v[k]] = '1';
					lines[v[k]] = 1;
					columns[v[k]] = 1;
					bk(k+1);
					queenTable[k][v[k]] = '0';
					lines[v[k]] = 0;
					columns[v[k]] = 0;
			}
		}
		v[k] = 0;
		return;
	}
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader fin = new BufferedReader(new FileReader("damesah.in"));
		
		n = Integer.parseInt(fin.readLine());
		fin.close();
		v = new int[n+1];
		lines = new int[n+1];
		columns = new int[n+1];
		queenTable = new char[n+2][n+2];
		configuration = new ArrayList<Integer>();
		for (int i = 0; i <= n+1; i++) {
			for (int j = 0; j <= n+1; j++) {
				queenTable[i][j] = '0';
			}
		}
		bk(1);
		BufferedWriter fout = new BufferedWriter(new FileWriter("damesah.out"));
		for (int i = 0; i < configuration.size(); i++) {
			fout.write(Integer.toString(configuration.get(i)) + " ");	
		}
		fout.write("\n"+Integer.toString(counter)+"\n");
		fout.close();
	}
}