#include <iostream>
#include <stdio.h>
#include <cstdio>
#include <fstream>

using namespace std;
int b[15],a[15], n, ap[15], cont=0, d=0;
int dp[30], ds[30];

void afis(int v[])
{
    for(int i=1; i<=n; i++)
        cout<<v[i]<<" ";
    printf("\n");
}

void creare(int v[])
{
    for(int i=1; i<=n; i++)
        v[i]=i;
}

/*int valid(int v[])
{
    for(int i=0; i<n-1; i++)
        for(int j=i+1; j<n; j++)
    {
        if((v[j]-v[i]==j-i) || (v[i]-v[j]==j-i))
            return 0;
    }
    return 1;
}*/

void bt(int k) ///generare de permutari
{   int i,j;
    if(k==n+1)
    {
        if(d==0)
        {
            d++;
            afis(b);
        }

        cont++;
        return;
    }
    else
    {   for(int l=1; l<=n; l++)
        {   j=a[l];
            i=k;
            if(ap[l]==0 && dp[j-i+n]==0 && ds[i+j-1]==0)
            {
                b[k]=a[l];
                ap[l]++;
                dp[j-i+n]=1;
                ds[i+j-1]=1;
                bt(k+1);

            b[k]=0;
            dp[j-i+n]=0;
            ds[i+j-1]=0;
            ap[l]=0;
            }
        }
    }

}

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

    scanf("%d", &n);
    creare(a);
    bt(1);
    cout<<cont;

    return 0;
}