#include <fstream>
#include <climits>
using namespace std;
ifstream in("damesah.in");
ofstream out("damesah.out");
int n,sol,ok,s[15];
bool in_mat(int x,int y)
{
    return (x<=n && x>=1 && y<=n && y>=1);
}
int verif(int linie)
{
    int lin,a,b;
    for (int i=1; i<=n; ++i)
        if (i!=linie && s[i]==s[linie])
            return 0;
    /// verificare inutila - de aici
    lin=linie+1;
    a=s[linie]-1;
    b=s[linie]+1;
    while (lin<=n)
    {
        if (s[lin]==a || s[lin]==b)
            return 0;
        a--;
        b++;
        lin++;
    }
    /// verificare inutila - pana aici
    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]=INT_MIN;
    }
}
int main()
{
    for (int i=0; i<=15; ++i)
        s[i]=INT_MIN;
    in>>n;
    dame(1);
    out<<"\n"<<sol;
}