#include <fstream>
#define mx 14
using namespace std;

ifstream f("dame.in");
ofstream g("dame.out");

int n, sol[mx], dame[mx], k;// i linia || dame[i] coloana
bool ok=true, MD[mx], L[mx], SD[mx];

void Read()
{
    f>>n;
}

void Print()
{
    for(int i=1;i<=n;++i)
    {
        g<<dame[i]<<' ';
    }
}

bool OK(int coloana,int linie )
{
    if(SD[linie+coloana]) return 0;
    if(L[linie]) return 0;
    if(MD[n+linie-coloana]) return 0;
    return 1;
}

void Back(int poz)
{
    if(poz==n+1)
    {
        if(ok)
        {
            ok=false;
            Print();
        }
        k++;
    }
    else
    {
        for(int i=1;i<=n;i++)
        {
            dame[poz]=i;
            if(OK(poz,i))
            {
                SD[i+poz]=L[i]=MD[n+i-poz]=1;
                Back(poz+1);
                SD[i+poz]=L[i]=MD[n+i-poz]=0;
            }
        }
    }

}

int main()
{
    Read();
    Back(1);
    g<<'\n'<<k;
    f.close();
    g.close();
    return 0;
}