#include <fstream>
using namespace std;
ifstream cin("damesah.in");
ofstream cout("damesah.out");
int n,v[20],ras,col[20],diagp[50],diags[50];
void bkt(int k)
{
    if(k==n+1)
    {
        ras++;
        if(ras==1)
        {
            for(int i=1; i<=n; i++)
            {
                cout<<v[i]<<' ';
            }
            cout<<'\n';
        }
    }
    else
    {
        for(int i=1;i<=n;i++)
        {
            if(col[i]==0 && diagp[n+k-i]==0 && diags[k+i]==0)
            {
                col[i]=1;
                diagp[n+k-i]=1;
                diags[k+i]=1;
                v[k]=i;
                bkt(k+1);
                col[i]=0;
                diagp[n+k-i]=0;
                diags[k+i]=0;
            }
        }
    }
}
int main()
{
    cin>>n;
    bkt(1);
    cout<<ras;
    return 0;
}