#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];

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)
{
    int p=Sol[k]+1;
    int j=Sol[k]-1;
    for(int i=k-1;i>=1;i--)
        {
            if(Sol[i]==Sol[k])
                    return false;
            if(Sol[i]==p || Sol[i]==j)
                    return false;
            p++;
            j--;
        }
    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);
                }
        }
}

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