#include <iostream>
#include <vector>
#include <fstream>
#include <cmath>

#define NMAX 14

using namespace std;

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

int n, cnt, sol[NMAX];
bool col[NMAX], main_diag[NMAX], sec_diag[NMAX];


void printSol(){
    for(int i= 1; i <= n; i++){
        out << sol[i] << " ";
    }
    out << '\n';
}

bool cont(int c, int k){
    if(!col[c] && !main_diag[c - k + n - 1] && !sec_diag[c + k])
            return true;

    return false;
}

void back(int k){
    if(k == n + 1){
       // cout << cnt << " ";
        cnt ++;
        if(cnt == 1){
            printSol();
        }
    }
    else {
        for(int i = 1; i<=n; i++ ){

          //  printSol();
            if(cont(i, k)){
                sol[k] = i;
                col[i] = main_diag[i - k + n -1] = sec_diag[i + k] = true;
                back(k+1);
                col[i] = main_diag[i - k + n - 1] = sec_diag[i + k] = false;
            }

        }
    }
}

int main() {
    in >> n;
    back(1);
    out << cnt << " ";
    return 0;
}