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

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

int n,cnt;
int st[25],viz[25];

bool valid(int top, int i)
{
    if(viz[i])
        return false;
    for(int j=1;j<top;j++)
    {
        if(abs(j-top)==abs(i-st[j]))
            return false;
    }
    return true;

}

void backt(int top)
{
    if(top==n+1)
    {
        cnt++;
        if(cnt==1){
            for(int i=1;i<=n;i++)
            {
                out<<st[i]<<" ";
            }
            out<<'\n';
        }
        return;
    }
    for(int i=1;i<=n;i++)
    {
        if(valid(top,i))
        {
            st[top]=i;
            viz[i]=1;
            backt(top+1);
            viz[i]=0;
        }
    }

}

int main()
{
    in>>n;
    backt(1);
    out<<cnt;
    return 0;
}