#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;
}

/*#include<cstdio>
#include<cmath>
using namespace std;

int x[30],n,nr,steag=1;

FILE *f=fopen("damesah.in","r");
FILE *g=fopen("damesah.out","w");

int valid(int k)
{
    int i;
    for(i=1;i<k;i++)
        if(x[i]==x[k]||k-i==abs(x[k]-x[i]))
            return 0;
    return 1;
}

void display_sol()
{
    int i;
    for(i=1;i<=n;i++)
        fprintf(g,"%d ",x[i]);
    fprintf(g,"\n");
}

void dame(int k)
{
    for(x[k]=1;x[k]<=n;x[k]++)
       if(valid(k))
            if(k==n)
            {
                if(steag==1)
                {
                    display_sol();
                    steag=0;
                }
                nr++;
            }
            else
                dame(k+1);
}

int main()
{
    fscanf(f,"%d",&n);
    dame(1);
    fprintf(g,"%d",nr);
    return 0;
}*/