#include<fstream>
#include<iostream>
#include<cmath>
using namespace std;
int n,c[20],nrSol;

void afisare()
{

    for(int i=1;i<=n;i++)printf("%d ",c[i]);
}
void dama(int k)
{

    int i,j,ok;
    if(k==n+1){
    if(nrSol==0)afisare();

     nrSol++;
    }
    else
    {
        for(int i=1;i<=n;i++)
        {
            for(ok=1,j=1;j<k;j++)
                if(abs(c[j]-i)==(k-j)||c[j]==i)ok=0;
            if(ok==1)
            {
                c[k]=i;
                dama(k+1);
            }
        }
    }
}
int main()
{
    freopen("damesah.in", "r", stdin);
    freopen("damesah.out", "w", stdout);

    scanf("%d",&n);
    dama(1);
    printf("\n%d",nrSol);
    return 0;
}