#include <iostream>
#include <fstream>
#define NUM 15
int C[NUM], nrs, prima, sol[NUM], n;
using namespace std;
int md(int a)
{
    if(a < 0)
        return -a;
    return a;
}
void copiere()
{
    for(int i = 1; i <= n; ++i)
        sol[i] = C[i];
}
void dame(int k)
{
    if(k == n + 1)
    {
        if(!prima)
        {
            copiere();
            prima = 1;
        }
        nrs++;
    }
    else
    {
        int ok, i, j;
        for(int i = 1; i <= n; ++i)
        {
            C[k] = i;
            ok = 1;
            for(int j = 1; j < k && ok; ++j)
                if(C[k] == C[j] || (md(C[k] - C[j]) == k - j))
                    ok = 0;
            if(ok == 1)
                dame(k + 1);
        }
    }
}
int main()
{
    ifstream f("damesah.in");
    ofstream g("damesah.out");
    f >> n;
    dame(1);
    for(int i = 1; i <= n; ++i)
        g << sol[i] << " ";
    g << "\n" << nrs;
    f.close();
    g.close();
}