#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++;
}

void BKT(int vf)
{   if(vf==n+1)
    {   Afis();
        return;
    }
    for(int i=1; i<=n; i++)
        if(!viz[i])
        {   viz[i]=true;
            st[vf]=i;
            bool ok=true;
            for(int i=1; i<vf; i++)
                if(abs(vf-i)==abs(st[vf]-st[i]))
                    ok=false;
            if(ok)
                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;
}