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

using namespace std;

ifstream in("damesah.in");
ofstream out("damesah.out");

int n,r;
int M[20][20];
vector<int> SOL;
bool C[20],D1[40],D2[40];
bool first=1;

bool can_place(int x, int y){
    if(!C[y]&&!D1[x-y+n]&&!D2[x+y-1])
        return 1;
    return 0;
}
void place(int x, int y){
    C[y]=D1[x-y+n]=D2[x+y-1]=1;
}
void remove(int x, int y){
    C[y]=D1[x-y+n]=D2[x+y-1]=0;
}
void bkt(int l){
    if(l==n+1)
        if(first){
            first=0;
            for(auto x : SOL)
                out<<x<<" ";
            out<<"\n";
            r++;
        }
        else r++;
    for(int i=1;i<=n;i++){
        if(can_place(l,i)){
            place(l,i);
            if(first)SOL.push_back(i);
            bkt(l+1);
            if(first)SOL.pop_back();
            remove(l,i);
        }
    }
}
int main(){
    in>>n;
    bkt(1);
    out<<r;
    return 0;
}