#include<fstream>
using namespace std;
ifstream in ("damesah.in");
ofstream out ("damesah.out");
int g1[101][101],n,ok,lin[101],rez[101],col[101],dia1[101],dia2[101],g2[101][101],s,sol;
void back (int p) {
    if (p > n) {
        sol ++;
        if (ok == 0) {
            ok = 1;
            for (int i = 1; i <= n; i ++) {
                out << rez[i] <<" ";
            }
            out << "\n";
        }
    }
    else {
        int i = p;
        for (int j = 1; j <= n; j ++) {
            if (lin[i] == 0 && col[j] == 0 && dia1[ g1[i][j] ] == 0 && dia2[ g2[i][j] ] == 0 ) {
                lin[i] = 1;
                col[j] = 1;
                dia1[ g1[i][j] ] = 1;
                dia2[ g2[i][j] ] = 1;
                rez[i] = j;
                back (p+1);
                lin[i] = 0;
                col[j] = 0;
                dia1[ g1[i][j] ] = 0;
                dia2[ g2[i][j] ] = 0;
            }
        }

    }
}
int main (void) {
    in >> n;
    for (int i = 1; i <= n; i ++) {
        s++;
        for (int j = 1; j <= n; j ++) {
            g1[i][j] = j+s-1;
        }
    }
    s = 0;
    for (int i = 1; i <= n; i ++) {
        s++;
        for (int j = n, t = 0; j >= 1; j --, t++) {
            g2[i][j] = t+s;
        }
    }
    back (1);
    out << sol;
    return 0;
}