// http://www.infoarena.ro/problema/damesah
#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;
ifstream fin("damesah.in");
ofstream fout("damesah.out");
int N,v[20],ok,nr_sol;
bool col[20];
void bkt(int lin);
void afisare();
bool valid(int lin);
int main()
{
    fin>>N;
    bkt(1);
    fout<<nr_sol<<'\n';
    return 0;
}
void bkt(int lin) {
    if(lin==N+1) {
        if(ok==0) {
            afisare();
            ok=1;
        }
        nr_sol++;
    }
    else {
        for(int i=1;i<=N;i++)
            if (!col[i]) {
                v[lin]=i;
                col[i] = true;
                if(valid(lin)) bkt(lin+1);
                v[lin]=0;
                col[i] = false;
            }
    }
}
bool valid(int lin) {
    int i;
    for(i=1;i<lin;i++) {
        if(lin-i==abs(v[lin]-v[i])) return false;
    }
    return true;
}
void afisare() {
    for(int i=1;i<=N;i++) fout<<v[i]<<" ";
    fout<<endl;
}