#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 Write()
{   if(!findSol)
    {   findSol=true;
        for(int i=1; i<=n; i++)
            sol[i]=st[i];
    }
    nrSol++;
}

void BKT(int vf)
{   if(vf==n+1)
        Write();
    else
        for(int i=1; i<=n; i++)
            if(!viz[i])
            {   viz[i]=true;
                st[vf]=i;
                if(st[vf]!=vf)
                {   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;
    return 0;
}