#include <bits/stdc++.h>

using namespace std;

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

const int N = 15;

int n,v[N][N],Sol[N],viz[N],D1[N][N],D2[N][N];

bool isOk=false;

int ans=0;

void Print(int k)
{
    if(!isOk)
        {
            isOk=true;
            for(int i=1;i<=k;i++)
                    fout<<Sol[i]<<" ";
            fout<<'\n';
        }
    ans++;
}

bool Check(int k)
{
    if(viz[Sol[k]])
            return false;
    if(D1[k-1][Sol[k]-1] || D2[k-1][Sol[k]+1])
            return false;
    D1[k][Sol[k]]=D1[k-1][Sol[k]-1]+1;
    D2[k][Sol[k]]=D2[k-1][Sol[k]+1]+1;
    viz[Sol[k]]=true;
    return true;
}

void Back(int k)
{
    for(int i=1;i<=n;i++)
        {
            Sol[k]=i;
            if(Check(k))
                {
                    if(k==n)
                        Print(k);
                    else
                        Back(k+1);
                    viz[Sol[k]]=0;
                    D1[k][Sol[k]]=0;
                    D2[k][Sol[k]]=0;
                }
        }
}

int main()
{
    fin>>n;
    Back(1);
    fout<<ans<<'\n';
}