#include <iostream>
#include <fstream>
#include <cmath>

using namespace std;

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

int v[40],x[40],n,db=0;

bool f1(int p){
    for(int i =1;i<p;i++){
        if(p-i==abs(x[p]-x[i])) return 0;
    }
    return 1;
}

void f2(int p){
    if(p==n+1){
        db++;
        if(db==1){
            for(int i=1;i<=n;i++){
                fout<<x[i]<<' ';
            }
            fout<<endl;
        }
    }
    else{
        for(int i=1;i<=n;i++){
            if(v[i]==0){
                v[i]=1;
                x[p]=i;
                if(f1(p)) f2(p+1);
                v[i]=0;
            }
        }
    }
}

int main(void){
    fin>>n;
    f2(1);
    fout<<db;
    fin.close();
    fout.close();
}