#include <fstream>

using namespace std;

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

int modul(int x)
{
    if(x>=0)
        return x;
    else
        return -x;
}

int n,S[20];
int total;

void gen(int k)
{
    if (k==n)
    {
        if (total==0)
        {
            for (int i=1;i<=n;i++)
                g<<S[i]<<" ";
            g<<"\n";
        }
        total++;
    }
    else
        for (int i=1;i<=n;i++)
        {
            S[k+1]=i;
            int t;
            t=1;
            for (int j=1;j<=k;j++)
                if (S[k+1]==S[j] || modul(k+1-j)==modul(S[k+1]-S[j]))
                    t=0;
            if (t==1)
                gen(k+1);

        }
}
int main()
{
    f>>n;
    gen(0);
//    if(n==4) g<<2;
//    if(n==5) g<<10;
//    if(n==6) g<<4;
//    if(n==7) g<<40;
//    if(n==8) g<<92;
//    if(n==9) g<<352;
//    if(n==10) g<<724;
//    if(n==11) g<<2680;
//    if(n==12) g<<14200;
//    if(n==13) g<<73712;
    g<<total;
    f.close();
    g.close();
    return 0;
}