#include <fstream>

using namespace std;
int n,a[20],x[20],vizc[24],vizdp[26],vizds[26],sol1,rez[14],cont;
ifstream f("damesah.in");
ofstream g("damesah.out");

void citire()
{f>>n;}

void afisare(int k)
{if(sol1==0)
for(int i=1;i<=k;i++)
rez[i]=x[i];
cont++;
sol1++;
}

void backt(int k)
{
    if(k==n+1)
        afisare(k-1);
    for(int i=1; i<=n; i++)
        if(vizc[i]==0&&vizdp[n+k-i]==0&&vizds[i+k-1]==0)
        {
            x[k]=i;
    vizc[i]=1;
    vizdp[n+k-i]=1;
    vizds[k+i-1]=1;
            backt(k+1);
    vizc[i]=0;
    vizdp[n+k-i]=0;
    vizds[k+i-1]=0;
        }

}


int main()
{
    citire();
    backt(1);
    for(int i=1;i<=n;i++)
    g<<rez[i]<<" ";
    g<<'\n'<<cont;
    return 0;
}