#include<iostream>
#include<fstream>
#include<algorithm>
#include<bitset>
#include<math.h>
using namespace std;
bool b;
int cont;

ofstream so("damesah.out");
void afis(int n,int x[])
{
    int i;
    for(i=1;i<=n;++i)
        so<<x[i]<<' ';
    b=true;
}
void dame(int n)
{
    int i,k;
    int es,ec;
    k=1;
    int x[20];
    x[k]=0;
    while(k>0)
    {
        do
        {
            if(x[k]<n)
            {
                x[k]++;
                es=1;
                ec=1;
                for(i=1;i<k;++i)
                    if(x[i]==x[k]||abs(x[i]-x[k])==k-i)
                        ec=0;
            }
            else
                es=0;
        }
        while(es&&!ec);
        if(es)
            if(k==n)
            {
                if(!b)afis(n,x);
                ++cont;
            }
            else
                x[++k]=0;
        else
            --k;

    }
}
int main()
{
    ifstream si;
    si.open("damesah.in");

    int n;
    si>>n;
    dame(n);
    so<<'\n'<<cont<<'\n';
}