#include<fstream>
#include<iostream>
using namespace std;
ifstream fin("damesah.in");
ofstream fout("damesah.out");
int n,nr[20],e;
bool a[20][20],v[20];
void afisare()
{
    e++;
    if(e==1)
    {
        for(int a1=1;a1<=n;a1++)
        {
            fout<<nr[a1]<<" ";
        }
        fout<<'\n';
    }
}
void verificare()
{
    int a2,ver=0,x1,y1;
    for(int a1=1;a1<=n;a1++)
    {
        a2=nr[a1];
        a[a1][a2]=1;
    }
    for(int a1=1;a1<=n;a1++)
    {
        x1=a1;
        y1=nr[a1];
        while(x1<n and y1>1)
        {
            x1++;
            y1--;
            if(a[x1][y1])
            {
                ver=1;
                break;
            }
        }
        if(ver==1) break;
        x1=a1;
        y1=nr[a1];
        while(x1<n and y1<n)
        {
            x1++;
            y1++;
            if(a[x1][y1])
            {
                ver=1;
                break;
            }
        }
        if(ver==1) break;
    }
    for(int a1=1;a1<=n;a1++)
    {
        a2=nr[a1];
        a[a1][a2]=0;
    }
    if(ver==0) afisare();
}
void fct(int x)
{
    if(x==n) verificare();
    else
    {
        x++;
        for(int a1=1;a1<=n;a1++)
        {
            if(v[a1]==0)
            {
                v[a1]=1;
                nr[x]=a1;
                fct(x);
                v[a1]=0;
            }
        }
    }
}
int main()
{
      fin>>n;
      fct(0);
      fout<<e;
}