#include <iostream>
#include <fstream>
using namespace std;

ifstream fin("damesah.in");
ofstream fout("damesah.out");

int d1[15], d2[15], n, x, y, c[15], st[100], nr=0;

void dame(int niv)
{
    if(niv==n+1)
    {
        if(nr==0)
        {
            for(int i=1; i<=n; i++)
            {
                fout<<st[i]<<" ";
            }
            fout<<'\n';
        }
        nr++;
        return;
    }
    {
        for(int j=1; j<=n; j++)
        {
            if(c[j]==0 && d1[niv+j]==0 && d2[j-niv+15]==0)
            {
                c[j]=1;
                d1[niv+j]=1;
                d2[j-niv+15]=1;
                st[niv]=j;
                dame(niv+1);
                c[j]=0;
                d1[niv+j]=0;
                d2[j-niv+15]=0;
            }
        }
    }
}

int main()
{
    fin>>n;
    dame(1);
    fout<<nr;


    return 0;
}