#include <iostream>
#include <fstream>
#include <cstdlib>
#include <ctime>

using namespace std;
ifstream in("damesah.in");
ofstream out("damesah.out");

#define ll long long
#define ull unsigned long long
#define ui unsigned int
#define pb push_back
const int NMax = 13 + 5;

int N,ans;
int queen[NMax];
bool diagP[2*NMax],diagS[2*NMax],col[NMax];

void backT(int);

int main() {
    in>>N;
    backT(1);
    out<<ans<<'\n';

    return 0;
}

void backT(int row) {
    if (row == N+1) {
        if (!ans) {
            for (int i=1;i <= N;++i) {
                out<<queen[i]<<' ';
            }
            out<<'\n';
        }

        ++ans;
        return;
    }

    for (int c=1;c <= N;++c) {
        if (!col[c] && !diagP[N + row - c] && !diagS[row+c]) {
            queen[row] = c;
            col[c] = diagP[N + row - c] = diagS[row+c] = true;

            backT(row+1);
            col[c] = diagP[N + row - c] = diagS[row+c] = false;
        }
    }
}