#include <cstdlib>
#include <fstream>

using namespace std;

int n,m,a[15][15],st[15],viz[15],cnt;

ofstream fout("damesah.out");

inline void Citire()
{
    ifstream fin("damesah.in");
    fin>>n;
    fin.close();
}

inline void Afisare()
{
    int i;
    cnt++;
    if(cnt==1)
    {
        for(i=1;i<=n;++i)
            fout<<st[i]<<" ";
        fout<<"\n";
    }
}

inline bool Valid(int k,int x)
{
    int i;
    if(viz[x]==1)
        return false;
    for(i=1;i<k;++i)
        if(abs(k-i)==abs(st[i]-x))
            return false;
    return true;
}

inline void Back(int k)
{
    int i;
    if(k==n+1)
        Afisare();
    else
    {
        for(i=1;i<=n;++i)
            if(Valid(k,i))
                {
                    st[k]=i;
                    viz[i]=1;
                    Back(k+1);
                    viz[i]=0;
                }
    }
}

int main()
{
    Citire();
    Back(1);
    fout<<cnt<<"\n";
    fout.close();
    return 0;
}