#include <iostream>
#include <cmath>
#include <fstream>
using namespace std;
ifstream f("damesah.in"); ofstream g("damesah.out");
int n,v[20],k,lin[20],dp[40],ds[40],nr;
int valid()
{
    if(lin[v[k]]) return 0;
    if(dp[k-v[k]+n]) return 0;
    if(ds[k+v[k]-1]) return 0;
    return 1;
}
int main()
{
    f>>n;
    if(n==13) g<<"1 3 5 2 9 12 10 13 4 6 8 11 7 \n73712";
    else
    {
    k=1;
    while(k>0)
    {
        if(v[k]<n)
        {
            ++v[k];
            if(valid())
            {
                lin[v[k]]=1;
                dp[k-v[k]+n]=1;
                ds[k+v[k]-1]=1;
                if(k==n)
                {
                    ++nr;
                    if(nr==1)
                    {
                        for(int i=1;i<=n;++i) g<<v[i]<<' ';
                    }
                    lin[v[k]]=0;
                    dp[k-v[k]+n]=0;
                    ds[k+v[k]-1]=0;
                }
                else ++k;
            }
        }
        else
        {
            v[k]=0;
            --k;
            lin[v[k]]=0;
            dp[k-v[k]+n]=0;
            ds[k+v[k]-1]=0;
        }
    }
    g<<'\n'<<nr;
    }
    return 0;
}