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 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()
{
    f>>n;
    backt(1);
    for(int i=1; i<=n; i++)
        g<<rez[i]<<" ";
    g<<'\n'<<cont;
    return 0;
}