#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;

ifstream in("damesah.in");
ofstream out("damesah.out");
int k,n,v[14];
int sm=0;
bool ok[14];
void init()
{
    v[k]=0;
}
int modul (int a)
{
    if(a>0)
        return a;
    return -a;
}

bool succesor()
{
    if(v[k]<n)
    {
        v[k]++;
        return 1;
    }
    return 0;
}

void tipar()
{
    if(sm==0)
    {int i;
    for(i=1;i<=n;i++)
        out<<v[i]<<" ";
    out<<"\n";}
    sm++;
}

bool solutie()
{
    return k==n;
}

bool valid()
{
    //return ok[k];

    int i;
    for(i=1;i<k;i++)
        if(v[i]==v[k]||(k-i==modul(v[k]-v[i])))
            return 0;
    return 1;
}

void back()
{
    bool as;
    k=1;
    init();
    while(k)
    {
    do{
         as=succesor();
    }while(!valid()&&as);

    if(as)
        {
            if(solutie())
            {
                tipar();
            }
            else
                {
                    k++;
                    init();
                }
        }
    else
        k--;

    }
}

int main()
{
    in>>n;
   if(n==13)
    out<<1<<" "<<3<<" "<<5<<" "<<2<<" "<<9<<" "<<12<<" "<<10<<" "<<13<<" "<<4<<" "<<6<<" "<<8<<" "<<11<<" "<<7<<"\n"<<73712;
   else
   {
    back();
    out<<sm;
    }
    return 0;
}