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

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

int n,a[15],sol,viz[15];

void afis()
{
    for(int i=1;i<=n;i++)
        out<<a[i]<<" ";
    out<<'\n';
}

bool verif(int val)
{
    if(val==1)
        return 1;
    for(int i=1;i<val;i++)
        if(abs(a[i]-a[val])==val-i)
        return 0;
    return 1;
}

void backtrack(int val)
{
    for(int i=1;i<=n;i++)
    if(viz[i]==0)
    {
        a[val]=i;
        viz[i]=1;
        if(verif(val))
        {
            if(val==n)
            {
                sol++;
                if(sol==1)
                    afis();
            }
            else backtrack(val+1);
        }
        viz[i]=0;
    }
}

int main()
{
    in>>n;
    backtrack(1);
    out<<sol<<'\n';
}