//GENERARE DE PERMUTARI PRIN BACKTRACKING ITERATIV

#include <iostream>
#include <cstdio>
#include <cmath>
#define Dmax 25
using namespace std;

int N,MIN,MAX,nr; int st[Dmax];

void back_dame()
{
    int as,ev,k,i;

    //GESTIONAREA STIVEI
    k=1; st[k]=MIN-1; //printf("%d %d",MIN,MAX);
    while(k)
    {
        as=1; ev=0;

        //ALEG UN ELEMENT VALID PENTRU NIVELUL k
        while(as==1 && ev==0)
        {
            if(st[k]<MAX)
            {
                st[k]=st[k]+1; as=1;
            }
            else as=0;

            if(as==1)
            {
                ev=1;
                for(i=1; i<k; i++)
                   {
                       if(st[i]==st[k]) ev=0;

                       if(abs(k-i)==abs(st[k]-st[i])) //SE ATACA DACA DIF DINTRE LINII E EGALA CU DIF DINTRE COLOANE
                          ev=0;
                   }
            }
        }

        if(as==0) k--;
        else
        {
            if(k==N) //AM COMPLETAT SI ULTIMUL NIVEL
            {
                nr++;
                if(nr==1) {for(i=1; i<=N; i++) printf("%d ",st[i]); printf("\n");}
            }
            else
            {
                k++; st[k]=MIN-1;
            }
        }
    }
}

int main()
{
    freopen("damesah.in", "r", stdin);
    freopen("damesah.out", "w", stdout);

    scanf("%d",&N);

    MIN=1; MAX=N; back_dame();
    printf("%d ",nr);

    return 0;
}