#include <iostream>
#include <fstream>

using namespace std;
ifstream fin ("damesah.in");
ofstream fout ("damesah.out");

int sol[20];
bool col[20];
bool diag1[20];
bool diag2[20];
int raspuns;

void dame (int linie, int n){

    if (linie > n){
        if (raspuns < 1){
            for (int i = 1; i <= n; ++i)
                fout << sol[i] << " ";
            fout << "\n";
        }
        raspuns++;
    }
    else
        for (int i = 1; i<= n; ++i)
            if (col[i] == 0 && diag1[i-linie+n-2] == 0 && diag2[linie+i-1] == 0) {
                sol[linie] = i;
            col[i] = 1;
            diag1[i-linie+n-2] = 1;
            diag2[linie+i-1] = 1;
            dame(linie+1,n);
            col[i] = 0;
            diag1[i-linie+n-2] = 0;
            diag2[linie+i-1] = 0;
        }

}

int main (){

    int n;
    fin >> n;
    dame(1,n);
    fout << raspuns;

    return 0;
}