#pragma GCC optimize("O3")
#pragma comment(linker, "/stack:200000000") // A lot of recursion
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
using namespace std;
#define fileIO(name) \
    freopen(name".in", "r", stdin); \
    freopen(name".out", "w", stdout);

short int n,Tabla[50][50],Locatia[50],RandulActual=1;
bool Rand[50],DiagonalaSec[101],DiagonalaPrin[101],k=1;
long long solutii;

inline bool verifica(short int i, short int j) { // verifica daca putem plasa o regina pe i j
    return !Rand[i] && !DiagonalaSec[i+j] && !DiagonalaPrin[((n<<1)-1)+i-j];
}
void ModificaStarea(short int i, short int j, bool valoare) {
    DiagonalaSec[i+j] = valoare;
    DiagonalaPrin[((n<<1)-1)+i-j] = valoare;
    Rand[i] = valoare;
}
short int Start(){
    int i = RandulActual;
    while (i <= n && Rand[i]) ++i;
    if(i>1) return i;
    return 1;
}

void Afiseaza(){
    for(short int i = 1; i <= n; i++) {
        for(short int j = 1; j <= n; j++)
            cout << Tabla[i][j] << " ";
        cout << "\n";
    }
}

void prelucrare( short int j) {
    for(short int i = RandulActual; i <= n; i++) {
        Locatia[j] = i; //  setam locatia reginei pe coloana j
        Tabla[i][j] = 1; // setam urmatoarea locatie a reginei pe tabla
        if(verifica(i, j)) {
            if(j == n){// daca am ajuns pe ultima coloana
                //Afiseaza();
                if(k){
                for(short int i = 1; i <= n; i++)
                    cout << Locatia[i]<<" ";
                cout << "\n";
                k=0;
                }
                ++solutii;
            }
            ModificaStarea(i, j, true);//marcam zona ca una folosita
            int temp = RandulActual; // memoram randul anterior
            RandulActual = Start(); // gasim urmatorul rand
            prelucrare( j+1); // cautam urmatoarea pozitie pe coloana
            Locatia[j] = 0; // stergem locatia
            ModificaStarea(i, j, false); // o marcam ca nefolosita
            RandulActual = temp; // ne intoarcem inapoi
            Tabla[i][j] = 0; // stergem regina

        }
        else
            Locatia[j] = 0,Tabla[i][j] = 0; // stergem regina
    }
}

int main() {
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    fileIO("damesah");
    cin >> n;
    for(short int i = 1; i <= n; i++)
        Locatia[i] = 0;
    prelucrare(1);
    cout << solutii;
    return 0;
}