#include <iostream>
#include <vector>
#include <fstream>
#include <cmath>
using namespace std;

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

int n, cnt;
vector <int> sol;

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

bool cont(int k){
    for(int i = 1; i < k; i++){
        if((sol[i] == sol[k]) || (abs(sol[i]-sol[k]) == (k - i)))
            return false;

    }
    return true;
}

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

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