#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;
ifstream fin("damesah.in");
ofstream fout("damesah.out");
int N,st[20];
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,ok;
    ok=1;
    for(i=1; i<nivel; i++)
    {
        if(st[i]==st[nivel]||(nivel-i==abs(st[nivel]-st[i])))
            ok=0;
    }
    return ok;
}
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
                {
                    nivel++;
                    init(nivel);
                }
            }
        }
        else
        {
            nivel--;
        }
    }
    return nr;
}
int main()
{
    int nr;
    fin>>N;
    nr=bk();
    fout<<nr;
}