#include<cstdio>
using namespace std;
const int NMAX=20;
int n,sol,v[NMAX];
bool col[NMAX],pr[NMAX*2],sec[NMAX*2];
bool verificare(int l, int c){
    if(col[c]==false && pr[l-c+n-1]==false && sec[l+c]==false)
        return true;
    return false;
}
void rezolvare(int ind, bool &ok){
    if(ind>n){
        if(ok){
            for(int i=1;i<=n;i++)
                printf("%d ", v[i]);
            printf("\n");
        }
        sol++;
        ok=false;
        return ;
    }
    for(int i=1;i<=n;i++){
        if(verificare(ind, i)==true){
            v[ind]=i;
            col[i]=pr[ind-i+n-1]=sec[i+ind]=1;
            rezolvare(ind+1, ok);
            col[i]=pr[ind-i+n-1]=sec[i+ind]=0;
        }
    }
}
int main(){
    freopen("damesah.in","r",stdin);
    freopen("damesah.out","w",stdout);
    bool ok=true;
    scanf("%d", &n);
    rezolvare(1, ok);
    printf("%d", sol);
    return 0;
}