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

int x[30],n,nr=0,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++;
                nr++;
            }
            else
                dame(k+1);
}

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