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