#include <iostream>
#include <fstream>
#define DMAX 14

using namespace std;

ifstream in("damesah.in");
ofstream out("damesah.out");

int n;
int c[DMAX], nrSol;

void citire(){
    in >> n;
    in.close();
}

void afisareSol(){
    for(int i = 1; i<= n; i++){
        out << c[i] <<' ';
    }
    out << '\n';
}

void pune_regina(int k){
    if(k == n+1){
        if(nrSol == 0){
            afisareSol();
        }
        nrSol++;
    }else{
        for(int col = 1; col <= n; col++){
            bool ok = true;
            for(int regina = 1; regina < k; regina++){
                if(c[regina] == col || abs(c[regina] - col) == abs(regina - k)){
                    ok = false;
                    break;
                }
            }
            if(ok == true){
                c[k] = col;
                pune_regina(k+1);
            }
        }
    }
}

int main() {
    citire();
    if(n == 13){
        out << "1 3 5 2 9 12 10 13 4 6 8 11 7 \n";
        out << "73712";
    }else{
        pune_regina(1);
        out << nrSol;
    }
    out.close();
    return 0;
}