#include<fstream>
#include<cmath>
using namespace std;
ifstream f("damesah.in");
ofstream g("damesah.out");
int n,v[20],sol;
void afisare()
{
    ++sol;
    if(sol==1){
        for(int i=1;i<=n;++i)g<<v[i]<<" ";
        g<<'\n';
    }
}
int verif(int k)
{
    for(int i=1;i<k;++i)
    {
        if(v[i]==v[k] or(k-i==abs(v[k]-v[i])))
            return 0;
    }
    return 1;
}
void bt(int k)
{
    if(k==n+1)
        afisare();
    else
        for(int i=1;i<=n;++i){
                v[k]=i;
                if(verif(k))
                    bt(k+1);
            }
}
int main()
{
    f>>n;
    bt(1);
    g<<sol<<'\n';
    return 0;
}