#include <iostream>
#include <fstream>
#include <cmath>

using namespace std;

ifstream f("damesah.in");
ofstream g("damesah.out");
int nr,x[14],n;
int afisare()
{
    int i;
    for(i=1; i<=n; i++)
        g<<x[i]<<" ";
}
int valid(int k)
{
    int i;
    for(i=1; i<k; i++)
        if((x[i]==x[k]) or (k-i==abs(x[k]-x[i])))
            return 0;
    return 1;
}
int backt(int n)
{
    int solutie=0,k,solutii=0;
    int prima=1;
    k=1;
    x[k]=0;
    while(k>0)
    {
        solutie=0;
        while(x[k]<n and !solutie)
        {
            x[k]++;
        solutie=valid(k);
        }
        if(!solutie)
            k--;
        else
        {
            if(k==n)
            {
                if(prima)
                {
                    prima=0;
                    afisare();
                }
                solutii++;
            }
            else
            {
                k++;
                x[k]=0;
            }
        }
    }
    return solutii;
}
int main()
{
    f>>n;
    nr=backt(n);
    g<<endl<<nr;
    return 0;
}