#include <bits/stdc++.h>

using namespace std;

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

int n;
int s[15];
int diagprin[35];
int diagsec[35];
int col[15];
int nrsol;
int ok(int i, int j)
{

    if(col[j]==1)
        return 0;
    if(diagprin[i+j-1]==1)
        return 0;
    if(diagsec[n-i+j]==1)
        return 0;
    return 1;

}

void bk(int pas)
{
    if(pas==n+1)
    {
        ++nrsol;
        if(nrsol==1)
        {
            for(int i=1; i<=n; ++i)
                g<<s[i]<<" ";
            g<<"\n";
        }

    }

    for(int i=1; i<=n; ++i)
    {
        if(ok(pas, i))
        {
            diagprin[pas+i-1]=1;
            col[i]=1;
            diagsec[n-pas+i]=1;
            s[pas]=i;
            bk(pas+1);
            diagprin[pas+i-1]=0;
            col[i]=0;
            diagsec[n-pas+i]=0;
        }
    }
}

int main()
{
    f>>n;
    bk(1);
    g<<nrsol;
    return 0;
}