#include <iostream>
#include <fstream>

using namespace std;

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

bool a[30], ok=1;
int n, sol, v[30];

int abs(int x){
     if(x < 0)
          return -x;
     return x;
}

int check(int ii, int jj){
     int ok2=1;

     for(int i=1; i < ii && ok2 == 1; i++)
          if(jj == v[i] || abs(ii - i) == abs(jj - v[i]))
               ok2=0;

     return ok2;
}

void bt(int k){
     if(k > n){
          if(ok == 1){
               for(int i=1; i<=n; i++)
                    fout<<v[i]<<" ";
               ok=0;
          }
          sol++;
          return;
     }

     for(int i=1; i<=n; i++)
          if(a[i] == 0 && check(k, i) == 1){
               a[i]=1;
               v[k]=i;
               bt(k+1);
               a[i]=0;
          }
}

int main (){
     fin>>n;
     bt(1);
     fout<<"\n"<<sol;
     return 0;
}