#include <fstream>
using namespace std;

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

int n,afisat,nrsol;//sunt automat 0

#define MAXN 13

char fcol[MAXN+1],fdiagp[2*MAXN+1],fdiags[2*MAXN+1];
int sol[MAXN+1];

void afis(int nr,int v[]){
  for(int i=1;i<=nr;i++){
    cout<<v[i]<<" ";
  }
  cout<<"\n";
}

void bkt(int k){
  int col;
  if(k==n+1){
    if(afisat==0){
      afis(k-1,sol);
      afisat=1;
    }
    nrsol++;
  }else{
    for(col=1;col<=n;col++){
      if(fcol[col]==0&&fdiagp[col+k]==0&&fdiags[n-col+k]==0){
        fcol[col]=fdiagp[col+k]=fdiags[n-col+k]=1;
        sol[k]=col;
        bkt(k+1);
        fcol[col]=fdiagp[col+k]=fdiags[n-col+k]=0;
      }
    }
  }
}

int main(){
  cin>>n;

  bkt(1);
  cout<<nrsol<<"\n";

  return 0;
}