#include<fstream>
#include<algorithm>
using namespace std;

ifstream fin("damesah.in");
ofstream fout("damesah.out");

int sol,col[100],dp[100],ds[100],n,st[100];

int askdp(int i,int j)
{
    int aux=abs(i-j);
    if(i>j)
        aux+=4;
    return dp[aux];
}
int askds(int i,int j)
{
    return ds[i+j];
}
void putds(int i,int j,int val)
{
    ds[i+j]+=val;
}
void putdp(int i,int j,int val)
{
    int aux=abs(i-j);
    if(i>j)
        aux+=4;
    dp[aux]+=val;
}


void back(int niv)
{
    if(niv==n+1)
    {
        if(sol==0)
            {for(int i=1;i<=n;++i)
            {
                fout<<st[i]<<" ";
            }
            fout<<'\n';
            }
        sol++;
        return ;
    }
    for(int i=1;i<=n;++i)
    {
        if(col[i]==0&&askdp(niv,i)==0&&askds(niv,i)==0)
        {
            st[niv]=i;
            col[i]++;
            putdp(niv,i,1);
            putds(niv,i,1);
            back(niv+1);
            col[i]--;
            putdp(niv,i,-1);
            putds(niv,i,-1);
        }
    }
}




int main()
{
    fin>>n;
    back(1);
    fout<<sol<<'\n';


    return 0;
}