#include <fstream>
//#include <vector>
#include <cstring>

using namespace std;

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

int total = 0;

void solve(int n, int curr, int sol[], bool lc[], bool d1[], bool d2[]){
  if(curr == n + 1){
    total += 1;
    if(total == 1){
      for(int i = 1; i <= n; i++)
        cout << sol[i] << ' ';
      cout << '\n';
    }
    return;
  }
  else{
    for(int i = 1; i <= n; i++){
      if(lc[i] or d1[n - (curr - i)] or d2[curr + i -1])
        continue;
      sol[curr] = i;
      lc[i] = true;
      d1[n - (curr - i)] = true;
      d2[curr + i - 1] = true;
      solve(n, curr + 1, sol, lc, d1, d2);
      lc[i] = false;
      d1[n - (curr - i)] = false;
      d2[curr + i - 1] = false;
    }
  }
}

int main(){
  int n;
  cin >> n;
  int sol[n + 1];
  bool lc[n + 1];
  bool d1[2 * n];
  bool d2[2 * n];
  memset(sol, 0, sizeof(sol));
  memset(lc, 0, sizeof(lc));
  memset(d1, 0, sizeof(d1));
  memset(d2, 0, sizeof(d2));
  /*vector<int> sol(n + 1);
  vector<bool> lc(n + 1); //lines and columns
  vector<bool> d1(2 * n ); //diag 1
  vector<bool> d2(2 * n ); // diag 2*/
  solve(n, 1, sol, lc, d1, d2);
  cout << total << '\n';
}