#include <fstream>

using namespace std;
ifstream cin("damesah.in");
ofstream cout("damesah.out");
int n,ok,nr;
int x[20],f[20];
void dame(int pas)
{
    if(pas>n)
    {
        if(ok==0)
        {
            ok=1;
            for(int i=1;i<=n;i++)
            {
                cout<<x[i]<<" ";
            }
            cout<<'\n';
        }
        nr++;
    }
    else
    {
        for(int i=1;i<=n;i++)
        {
            x[pas]=i;
            if(f[i]==0)
            {
                int okk=0;
                for(int j=1; j<pas;j++)
                {
                        if(i-j>0 && x[pas-j]==i-j)
                        {
                            okk=1;
                        }
                        else if(i+j<=n && x[pas-j]==i+j)
                        {
                            okk=1;
                        }
                }
                if(okk==0)
                {
                    f[i]=1;
                    dame(pas+1);
                    f[i]=0;
                }
            }
        }
    }
}
int main()
{
    cin>>n;
    dame(1);
    cout<<nr;
    return 0;
}
/**
 0 2 0 0
 0 0 0 4
 1 0 0 0
 0 0 3 0
**/