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

using namespace std;

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

int n;
bool ocup[DMAX];//marcare coloane regina
bool ocupDiagPrinc[DMAX*2], ocupDiagSec[DMAX*2];//marcare diagonale regina
int solutie[DMAX], nrSol;

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

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

bool validare(int col, int lin){
    if(ocup[col]== false && ocupDiagPrinc[n + col - lin] == false &&
            ocupDiagSec[lin + col - 1] == false){
        return true;
    }
    return false;
}

void marcareRegina(int lin,int col, bool val){//marchez cu true cand pun regina pe tabla
    ocup[col] = val;                          //si cu false cand o scot
    ocupDiagPrinc[n + col - lin] = val;
    ocupDiagSec[col + lin - 1] = val;
}

void bkt(int lin){
    for(int col = 1; col <= n; col++){
        if(validare(col, lin) == true){
            solutie[lin] = col;
            marcareRegina(lin, col, true);
            if(lin == n){
                nrSol++;
                if(nrSol == 1) {
                    afisareSol();
                }
            }else{
                bkt(lin + 1);
            }
            marcareRegina(lin, col, false);
        }
    }
}

int main() {
    citire();
    bkt(1);
    out << nrSol;
    out.close();
    return 0;
}