#include <bits/stdc++.h>

using namespace std;

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

int n,NrSol,c[15],lin[15],dp[30],ds[30];
bool primsol=true;

void Afisare()
{
    int i,j;
    if(primsol)
    {
        for(i=1; i<=n; i++)
            fout << c[i] << " ";
        fout << '\n';
        primsol=false;
    }
}

void Plaseaza_Regina(int k)
{
    int i,j;
    if(k>n)
        Afisare(), NrSol++;
    else
    for(i=1;i<=n;i++)
    {
        if(lin[i] || dp[n-i+k] || ds[i+k-1])
            continue;
        lin[i]=dp[n-i+k]=ds[i+k-1]=1;
        c[k]=i;
        Plaseaza_Regina(k+1);
        lin[i]=dp[n-i+k]=ds[i+k-1]=0;
    }
}

int main()
{
    fin >> n;
    Plaseaza_Regina(1);
    fout << NrSol;
    return 0;
}