#include<cstdio>
#include<cmath>
#include<iostream>
using namespace std;
int ok=0;
int ko=0;

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

int main()
{  FILE *f=fopen("damesah.in","r");

    fscanf(f,"%d",&n);


    dame(1);

    fprintf(g,"%d",ko);

    return 0;
}