#include <fstream>

using namespace std;
const int NMAX=13;

ifstream f("damesah.in");
ofstream g("damesah.out");

int N, x[NMAX+1], nrSol;
bool C[NMAX+1],
     dP[2*NMAX],
     dS[2*NMAX];

void afis()
{
    for(int i=1; i<=N; i++)
        g<<x[i]<<' ';
    g<<'\n';
}

inline bool valid(int k)
{
    return C[x[k]]==0 && dP[N-k+x[k]]==0 && dS[k+x[k]-1]==0;
}

void backt()
{
    int k=1;
    x[1]=0;
    while(k>0)
    {
        if(x[k]<N)
        {
            x[k]++;
            if(valid(k))
            {
                C[x[k]]=dP[N-k+x[k]]=dS[k+x[k]-1]=1;
                if(k==N)
                {
                    if(nrSol==0) afis();
                    nrSol++;
                    C[x[k]]=dP[N-k+x[k]]=dS[k+x[k]-1]=0;
                    k--;
                    C[x[k]]=dP[N-k+x[k]]=dS[k+x[k]-1]=0;
                }
                else
                    x[++k]=0;
            }
        }
        else
        {
            k--;
            C[x[k]]=dP[N-k+x[k]]=dS[k+x[k]-1]=0;
        }
    }
}

int main()
{
    f>>N;
    backt();
    g<<nrSol;
    f.close();
    g.close();
    return 0;
}