#include <iostream>
#include <fstream>
using namespace std;
ifstream f ("damesah.in");
ofstream g ("damesah.out");
int v[14],n;
bool d1[50]={false},d2[50]={false},c[15]={false};
long long p=0;
bool pr = false;
void print()
{
    if (!pr)
    {
    for (unsigned int i=1; i<=n; i++)
        g<<v[i]<<" ";
    g<<"\n";
    pr=true;
    }
}
int succesor(int k)
{
    if (v[k]<n)
        {
            v[k]++;
            return 1;
        } else
    return 0;
}
int solutie(int k)
{
    return (k==n);
}
int valid(int k)
{
   if (( d1[8+(v[k]-k)])||(d2[v[k]+k-1])||(c[v[k]]))
        return 0;
   /* cl=k; cc=v[k];
    while ((cc<8)&&(cl<8))
    {
        cc++; cl++;
        if (v[cl]==cc)
            return 0;
    }
    cl=k; cc=v[k];
    while ((cc>1)&&(cl<8))
    {
        cc--; cl++;
        if (v[cl]==cc)
            return 0;
    }
*/
    return 1;
}
void Back(int n)
{
    bool afost[15]={false};
    int isV=0, isS=0, k=1;
    v[k]=0;
    while (k)
    {
        isS=0; isV=0;
        do
        {
            isS=succesor(k);
            if (isS)
                isV=valid(k);
        } while(isS&&!isV);
    if (isS)
        if (solutie(k))
            {
                print();
                p++;
            } else
        {
            c[v[k]]=true;
            afost[k]=true;
            d1[8+(v[k]-k)]=true;
            d2[v[k]+k-1]=true;
            k++;
            v[k]=0;
        } else
        {
            k--;
            if (afost[k])
            {
            c[v[k]]=false;
            d1[8+(v[k]-k)]=false;
            d2[v[k]+k-1]=false;
            afost[k]=false;
            }
        }
    }
}
int main ()
{
    f>>n;
    Back(n);
    g<<p;
    return 0;
}