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

const int Nmax=15;

int v[Nmax],col[Nmax],sol=0,n;

unordered_map<int,bool> d1,d2;

ofstream fout("damesah.out");

bool isValid(int i, int k) {
    return (col[i]==0 && d1[k-i]==0 && d2[k+i]==0);
}

void bkt(int k) {
    if (k==n+1) {
        sol++;
        if (sol==1) {
            for (int i=1; i<=n; ++i) {
                fout<<v[i]<<' ';
            }
            fout<<endl;
        }
    }
    else {
        for (int i=1; i<=n; ++i) {
            v[k]=i;
            if (isValid(i,k)) {
                col[i]=1;
                d1[k-i]=1;
                d2[k+i]=1;
                bkt(k+1);
                col[i]=0;
                d1[k-i]=0;
                d2[k+i]=0;
            }
        }
    }
}

int main()
{
    ifstream fin("damesah.in");
    fin>>n;
    bkt(1);
    fout<<sol;
    fin.close();
    fout.close();
    return 0;
}