#include<iostream>
#include<fstream>
using namespace std;
ifstream in("damesah.in");
ofstream out("damesah.out");
int n,ok,x[50][50],y[50][50],vizc[50],st[50],contor,vizds[100],vizdp[100],sol[50];
void back(int k)
{
    int i;
    if(k==n+1)
    {
        ok=0;
        contor++;
        for(i=1; i<=n; i++)
        {
            if(st[i]<sol[i])
            {
                ok=1;
            break;
            }

        else if (st[i]>sol[i])
            return;
        }
        if(ok==1)
            for(i=1; i<=n; i++)
            {
                sol[i]=st[i];
            }

        return ;
    }
    for(i=1; i<=n; i++)
    {
        if(vizc[i]==0&&vizdp[x[k][i]]==0&&vizds[y[k][i]]==0)
        {
            st[k]=i;
            vizc[i]=vizdp[x[k][i]]=vizds[y[k][i]]=1;
            back(k+1);
            vizc[i]=vizdp[x[k][i]]=vizds[y[k][i]]=0;
        }
    }

}
int main()
{
    int i,j;
    in>>n;
    for(i=1; i<=n; i++)
        sol[i]=n;
    for(i=1; i<=n; i++)
    {
        for(j=1; j<=n; j++)
        {
            x[i][j]=i+j-1;
        }
    }
    for(i=1; i<=n; i++)
    {
        for(j=1; j<=n; j++)
        {
            y[i][j]=j-i+n;
        }
    }
    back(1);
    for(i=1; i<=n; i++)
    {
        out<<sol[i]<<" ";
    }
    out<<'\n';
    out<<contor;
    return 0;
}