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

ifstream fin("damesah.in");
ofstream fout("damesah.out");
int n, sol[16], cnt, first = 0;
bool col_ocupata[15];
bool diag_principala[30];
bool diag_secundara[30];
void back(int line) {
    if (line == n + 1) {
        cnt++;
        if (!first) {
            for (int i=1; i<=n; i++)
                fout<<sol[i]<<' ';
            fout<<'\n';
            first = 1;
        }
        return;
    }
    for (int col = 1; col <= n; col++) {
        if (!col_ocupata[col] && !diag_principala[line - col + n] && !diag_secundara[line + col]) {
            sol[line] = col;
            col_ocupata[col] = true;
            diag_principala[line - col + n] = true;
            diag_secundara[line + col] = true;
            back(line + 1);
            col_ocupata[col] = false;
            diag_principala[line - col + n] = false;
            diag_secundara[line + col] = false;
        }
    }
}

int main(void) {
    fin>>n;
    back(1);
    fout<<cnt;
    return 0;
}