#include <cstdio>
#define Mlen 15
using namespace std;
FILE
*in=fopen("damesah.in","r"),
*out=fopen("damesah.out","w");
int n,nr,sol[Mlen];
bool dp[2*Mlen],ds[2*Mlen],col[Mlen];
bool ok(int y,int x)
{
    if(col[x])return 0;
    if(ds[y+x])return 0;
    if(dp[n-1-y+x])return 0;
    return 1;
}
void nextl(int l)
{
    if(l==n)
    {
    if(nr<1)for(int i=0;i<n;++i)fprintf(out,"%d ",sol[i]);
    ++nr;
    return;
    }
    for(int c=0;c<n;++c)
    {
        if(ok(l,c))
            sol[l]=c+1,
            col[c]=1,
            ds[c+l]=1,
            dp[n-1-l+c]=1,
            nextl(l+1),
            col[c]=0,
            ds[c+l]=0,
            dp[n-1-l+c]=0;
    }
}
int main()
{
    fscanf(in,"%d",&n);
    nextl(0);
    fprintf(out,"\n%d ",nr);
    return 0;
}