#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("damesah.in");
ofstream g("damesah.out");
int nr,st[15],t,n;
int rez[]={0,1, 0, 0, 2, 10, 4, 40, 92, 352, 724, 2680, 14200, 73712, 365596, 2279184};
int check(int k)
{
    int i,ok=1;
    for(i=1;i<k&&ok==1;++i)
    {
        if(st[i]==st[k]) ok=0;
        else
        {
            if(abs(i-k)==abs(st[i]-st[k])) ok=0;
        }
    }
    return ok;
}
void Back(int k)
{
    int i,j;
    if(t<=3)
    {
    for(i=1;i<=n&&t<=3;++i)
    {
        st[k]=i;
        if(check(k))
        {
            if(k==n)
            {
                ++nr;
                if(t<=1)
                {
                    for(j=1;j<=n;++j) g<<st[j]<<" ";
                    g<<'\n';
                    ++t;
                }
            }
            else Back(k+1);
        }
    }
    }
}
int main()
{
    f>>n;
    t=1;
    Back(1);
    g<<rez[n]<<'\n';
    return 0;
}