#include<fstream>
#define maxn 16
using namespace std;
ifstream fi("damesah.in");
ofstream fo("damesah.out");

int n,v[maxn],sol=0;

int modul(int x){
    if(x>=0) return x;
    else return(-x);
}

void tipar(int n){
     int i;
     for(i=1;i<=n;i++) fo<<v[i]<<" ";
     fo<<"\n";
}

bool valid(int k){
     int i;
     for(i=1;i<k;i++) 
       if(v[k]==v[i] || modul(v[i]-v[k])==k-i) return 0;
     return 1;
}

void back(int k){
     int i;
     if(n+1==k){
                sol++;
                if(sol==1) tipar(n);
               }
     else for(i=1;i<=n;i++){
                            v[k]=i;
                            if(valid(k)) back(k+1); 
                           }
}

int main(){
    fi>>n; 
    
    back(1);
    fo<<sol;
    
    fi.close();
    fo.close();
    return 0;
}