#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

ifstream fin("damesah.in");
ofstream fout("damesah.out");

const int NMAX = 15;

int N, nrs, Queen[NMAX], S[NMAX];
bool C[NMAX], MD[NMAX + NMAX], SD[NMAX + NMAX];

void Back(int K)
{
    if(K == N + 1)
    {
        if(!nrs)
            for(int i = 1; i <= N; i++)
                S[i] = Queen[i];
        nrs++;
    }
    else
    {
        for(int j = 1; j <= N; j++)
            if(!C[j] && !MD[K - j + N] && !SD[K + j])
            {
                C[j] = MD[K - j + N] = SD[K + j] = 1;
                Queen[K] = j;
                Back(K + 1);
                C[j] = MD[K - j + N] = SD[K + j] = 0;
            }
    }
}

int main()
{
    fin >> N;
    Back(1);

    for(int i = 1; i <= N; i++)
        fout << S[i] << ' ';
    fout << '\n' << nrs;
    return 0;
}