#include <bits/stdc++.h>
#define NM 20
using namespace std;
ifstream f("damesah.in");
ofstream g("damesah.out");

int n,nrSol,sol[NM],st[NM];
bool findSol,viz[NM],a[NM][NM];

void Afis()
{   if(!findSol)
    {   findSol=true;
        for(int i=1; i<=n; i++)
            sol[i]=st[i];
    }
    nrSol++;
}

bool ok(int x)
{   for(int i=1; i<x; i++)
        if(abs(x-i)==abs(st[x]-st[i]))
            return false;
    return true;
}

void BKT(int vf)
{   for(int i=1; i<=n; i++)
        if(!viz[i])
        {   viz[i]=true;
            st[vf]=i;
            if(ok(vf))
                (vf==n ? Afis() : BKT(vf+1));
            viz[i]=false;
        }
}

int main()
{   f>>n;
    BKT(1);
    for(int i=1; i<=n; i++)
        g<<sol[i]<<' ';
    g<<'\n'<<nrSol;
    f.close(); g.close(); return 0;
}