#include <fstream>
using namespace std;
ifstream in("damesah.in");
ofstream out("damesah.out");
int n,sol,ok,s[15];
int verif(int linie)
{
    int lin,a,b;
    for (int i=1; i<=n; ++i)
        if (i!=linie && s[i]==s[linie])
            return 0;
    lin=linie-1;
    a=s[linie]-1;
    b=s[linie]+1;
    while (lin>=1)
    {
        if (s[lin]==a || s[lin]==b)
            return 0;
        a--;
        b++;
        lin--;
    }
    return 1;
}
void dame(int lin)
{
    if (lin==n+1)
    {
        sol++;
        if (!ok)
        {
            for (int i=1; i<=n; ++i)
                out<<s[i]<<" ";
            ok=1;
        }
    }
    for (int i=1; i<=n; ++i)
    {
        s[lin]=i;
        if (verif(lin))
            dame(lin+1);
        s[lin]=0;
    }
}
int main()
{
    in>>n;
    dame(1);
    out<<"\n"<<sol;
}