#include <bits/stdc++.h>
using namespace std;

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

int v[17];
int n;
int ans=0;
int afis=0;
int f[17];

void afisare()
{
    for (int i=1;i<=n;i++)
        fout<<v[i]<<' ';
    fout<<'\n';
}

bool ok(int k)
{
    for (int i=1;i<k;i++)
    {
        if (k-i==abs(v[k]-v[i])) return 0;
    }
    return 1;
}

void bkt(int poz)
{
    for (int i=1;i<=n;i++)
    {
        v[poz]=i;
        if (ok(poz) && f[i]==0)
        {
            f[i]=1;
            if (poz==n)
            {
                ans++;
                if (afis==0) afisare(),afis=1;
            }
            else bkt(poz+1);
            f[i]=0;
        }
        //f[i]=0;
    }
}

int main()
{
    fin>>n;
    bkt(1);
    fout<<ans;
}