#include <fstream>
#include <cmath>
using namespace std;
ifstream fin("damesah.in");
ofstream fout("damesah.out");
int v[16];
int fr[17];
int con=0,n,a1;

int con1()
{
    if(fr[v[a1]]==0)
    {
        return 1;
    }
    return 0;
}

int con2()
{
    for(int i=1;i<a1;i++)
    {
        if(abs(i-a1)==abs(v[i]-v[a1]))
        {
            return 0;
        }
    }
    return 1;
}

void bkt()
{
    a1=1;
    while(a1)
    {
        if(v[a1]<n)
        {
            v[a1]++;
            if(con1())
            {
                if(con2())
                {
                    if(a1==n){
                    con++;
                    if(con==1)
                    {
                        for(int i=1;i<=n;i++)
                        {
                            fout<<v[i]<<" ";
                        }
                        fout<<endl;
                    }
                    }
                    else
                    {
                        fr[v[a1]]++;
                        a1++;
                    }
                }
            }
        }
        else
        {
            a1--;
            fr[v[a1]]=0;
            v[a1+1]=0;
        }
    }
}

int main()
{
    fin>>n;
    bkt();
    fout<<con;
    return 0;
}