#include <iostream>
#include <math.h>
#include <fstream>
using namespace std;

ifstream f("damesah.in");
ofstream gout("damesah.out");
void init(int s[100], int niv);
int succesor(int s[100],int niv);
int sol(int S[100],int niv);
int valid(int s[100],int niv);
void tipar(int s[100],int niv);

int k,st[100],n;
int times=0;
int main()

{
    int as,ev;
    f>>n;
    k=1;
    init(st,k);
    while(k>0)
    {
        do
        {
            as=succesor(st,k);
            ev=valid(st,k);
        }
        while(as && !ev);
        {
            if(as)
            {
                if(sol(st,k))
                {
                    tipar(st,k);
                }
                else
                {
                    k++;
                    init(st,k);
                }
            }
            else k--;
        }
    }
    gout<<times;
    gout.close();
    return 0;
}


void init(int s[100], int niv)
{
    s[niv]=0;
}
int succesor(int s[100],int niv)
{
    if(s[niv]==n)return 0;
    else
    {
        s[niv]++;
        return 1;
    }
}
int sol(int s[100],int niv)
{
    return (niv==n);
}
int valid(int s[100],int niv)
{
    int i,g=1,ok=1;
    for (i=1; i<niv; i++)
    {
        if(s[niv]==s[i])g=0;
        if(abs(s[i]-s[niv])==abs(i-niv))ok=0;
    }
    if(ok && g)return 1;
    return 0;
}
void tipar(int s[100],int niv)
{
    times++;
    if(times==1){
    for(int i=1; i<=niv; i++)
        gout<<s[i]<<' ';
    gout<<endl;
  }
}