#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],sol[13];
void Afisare(int n)
{
    for(i=1; i<=n; i++)
        sol[i]=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)
            {
                if(ok)
                    Afisare(n),ok=0;
                nrSol++;
            }
            else
                k++,c[k]=0;

        }
    }
    return nrSol;
}
    int main()
    {
         f>>n;
         int nrSol=PlasareDame(n);
         for(i=1;i<=n;i++)
            g<<sol[i]<<" ";
         g<<"\n";
         g<<nrSol;


        return 0;
    }