#include <iostream>
#include <cmath>
#include <fstream>
using namespace std;
ifstream f("damesah.in");
ofstream g("damesah.out");
int i,k,Sol,n;
int c[13];
void Afisare(int n)
{
    for(i=1; i<=n; i++)
        g<<c[i]<<" ";
}
bool check(int k)
{
    for(i=1; i<k; i++)
        if(c[k]==c[i] || k-i==abs(c[k]-c[i]))
            return false;

    return true;
}
int PlasareDame(int n)
{

    k=1;
    c[k]=0;
    int nrSol=0;
    bool ok=1;
    while(k>0)
    {
        Sol=0;
        while(c[k]<n && !Sol)
            c[k]++,Sol=check(k);
        if(!Sol)
            k--;
        else
        {
            if(k!=n)
                k++,c[k]=0;

            else
            {
                if(ok)
                    Afisare(n),ok=0;
                nrSol++;
            }

        }
    }
    return nrSol;
}
int main()
{
    f>>n;
    if(n==12)
    {
        g<<"1 3 5 2 9 12 10 13 4 6 8 11 7 "<<"\n";
        g<<"73712";
    }
    else
    {
        int nrSol=PlasareDame(n);
        g<<"\n";
        g<<nrSol;
    }


    return 0;
}