#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;
ifstream fin("damesah.in");
ofstream fout("damesah.out");
int N,st[20],fv[20],fvd[30],fvd2[30];
int init(int nivel)
{
    st[nivel]=0;
}
int exista(int nivel)
{
    if(nivel<=N&&st[nivel]<N)
        return 1;
    else
        return 0;
}
int validare(int nivel)
{
    int i;
    if(fv[st[nivel]]==0&&fvd[st[nivel]-nivel+N-1]==0&&fvd2[st[nivel]+nivel-1]==0)
        return 1;
    else
        return 0;
}
int rezultat(int nivel)
{
    if(nivel==N)
        return 1;
    else
        return 0;
}
int bk()
{
    int nivel,i,ok,nr;
    nivel=1;
    ok=0;
    nr=0;
    while(nivel>0)
    {
        if(exista(nivel))
        {
            st[nivel]++;
            if(validare(nivel))
            {
                if(rezultat(nivel))
                {
                    if(ok==0)
                    {
                        for(i=1; i<=N; i++)
                            fout<<st[i]<<" ";
                        fout<<'\n';
                        ok=1;
                    }
                    nr++;
                }
                else
                {
                    fv[st[nivel]]=1;
                    fvd[st[nivel]-nivel+N-1]=1;
                    fvd2[st[nivel]+nivel-1]=1;
                    nivel++;
                    init(nivel);
                }
            }
        }
        else
        {

            nivel--;
            fv[st[nivel]]=0;
            fvd[st[nivel]-nivel+N-1]=0;
            fvd2[st[nivel]+nivel-1]=0;
        }
    }
    return nr;
}
int main()
{
    int nr;
    fin>>N;
    nr=bk();
    fout<<nr;
}