#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
FILE *f=fopen("damesah.in","r");
int n,x[15],nr=0;
int valid(int k)
{
    for(int i=1;i<k;i++)
        if(x[i]==x[k]||k-i==abs(x[k]-x[i]))
            return 0;
        return 1;
}
FILE *f1=fopen("damesah.out","w");
void afish()
{
    nr++;
    if(nr==1)
    for(int i=1;i<=n;i++)
       fprintf(f1,"%d ",x[i]);



}
void back(int k)
{
    for(x[k]=1;x[k]<=n;x[k]++)
    {
        if(valid(k))
            if(k==n)
              afish( );
            else
                back(k+1);

    }
}

int main()
{
    fscanf(f,"%d",&n);
    back(1);
    fprintf(f1,"\n%d",nr);
    return 0;
}