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

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

int nrsol = 0;
int visited_column[30], visited_main[30], visited_secondary[30];

vector <int> solution;

int backtracking(int line, int n){
    if(line == n + 1){
        if(nrsol == 0){
            for(auto &elem : solution){
                cout << elem << " ";
            }
            cout << "\n";
        }
        nrsol ++;
    }
    else {
        for(int j = 1; j <= n; j ++){
            int main_label = line - j + n;
            int secondary_label = line + j;
            if(visited_column[j] == 0 && visited_main[main_label] == 0 && visited_secondary[secondary_label] == 0){
                visited_column[j] = 1;
                visited_main[main_label] = 1;
                visited_secondary[secondary_label] = 1;
                solution.push_back(j);
                backtracking(line + 1, n);
                solution.pop_back();
                visited_column[j] = 0;
                visited_main[main_label] = 0;
                visited_secondary[secondary_label] = 0;
            }
        }
    }
    return nrsol;
}

int main() {
    int n;
    cin >> n;
    backtracking(1, n);
    cout << nrsol;
    return 0;
}