#include<fstream>
#include<iostream>
using namespace std;
int st[150],n,i,c;
ifstream fin("damesah.in");
ofstream fout("damesah.out");
void initiere()
{
    i++;
    st[i]=0;
}
int succesor()
{
    if(st[i]+1<=n && i<=n)
    {
        st[i]++;
        return 1;
    }
    else
    {
        return 0;
    }
}
int valid()
{
    for(int j=1; j<i; j++)
    {
        if(((st[i]-st[j])==(i-j))||((st[i]-st[j])==(j-i))||(st[i]==st[j]))
        {
            return 0;
        }
    }
    return 1;
}
int solutie()
{
    if(i==n)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
void tipar()
{
    for(int j=1;j<=n;j++)
    {
        fout<<st[j]<<" ";
    }
    fout<<"\n";
}
int main ()
{
    fin>>n;
    i=0;
    initiere();
    while(i>0)
    {
        int as,ev;
        do
        {
            as=succesor();
            ev=valid();
        }
        while(as==1 && ev==0);
        if(as==1)
        {
            if(solutie())
            {
                c++;
                if(c==1)
                tipar();
            }
            else
            {
                initiere();
            }
        }
        else
        {
            i--;
        }
    }
    fout<<c;
    fout.close();
    fin.close();
    return 0;
}