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

using namespace std;

bool is_valid(int col, int step, vector<int>& sol) {
    for (int i = 1; i < step; i++) {
        if (sol[i] == col) {
            return false;
        }
        if (abs(sol[i] - col) == abs(i - step)) {
            return false;
        }
    }
    return true;
}

void bkt(int step, int stop, vector<int>& sol, int& count, ofstream& fout) {
    if (step > stop) {
        if (count == 0) {
            for (int i = 1; i <= stop; i++) {
                fout << sol[i] << " ";            
            }
            fout << "\n";
        }
        count++;
    }
    for (int col = 1; col <= stop; col++) {
        if (is_valid(col, step, sol)) {
            sol[step] = col;
            bkt(step+1, stop, sol, count, fout);
        }
    }
}

int main() {
    ifstream fin("damesah.in");
    ofstream fout("damesah.out");

    int n;
    int count = 0;
    fin >> n;
    vector<int> sol(n + 1, 0);
    bkt(1, n, sol, count, fout);
    fout << count;
    fin.close();
    fout.close();
}