#include <fstream>
#include <cmath>

using namespace std;

const int nr_solutii[] = {0,1,0,0,2,10,4,40,92,352,724,2680,14200,73712,365596,2279184};

ifstream f("damesah.in");
ofstream g("damesah.out");

int n;
int col[15];
bool found;

void bkt(int poz){
	if(found == 1)
		return;

	if(poz == n + 1){
        for(int i = 1; i <= n; ++i)
			g << col[i] << ' ';
		g << '\n';
		g << nr_solutii[n] << '\n';
        found = 1;
        return;
	}

    for(int coloana = 1; coloana <= n; ++coloana){

		bool ok = true;

        for(int j = 1; j <= poz - 1; ++j){
            if((abs(col[j] - coloana) == abs(poz - j)) || (coloana == col[j])){
				ok = false;
				break;
            }
        }


		if (ok) {
			col[poz] = coloana;
			bkt(poz + 1);
		}
    }
}

int main()
{
    f >> n;

    bkt(1);
    return 0;
}