#include <stdio.h>
#include <vector>
#include <iostream>
#include <cstring>
#include <unordered_map>
using namespace std;
int8_t hashes[150], firstDiags[305], secondDiags[305], n, sols[150], checker;
uint32_t total;

int8_t getDiag(int8_t y, int8_t x) {
  return firstDiags[x + y] || secondDiags[x + (n - 1 - y)];
}

void generateSolutions(int8_t k) {
  if(n == k) {
    total++;
    if(!checker) {
      for(int8_t i = 0; i < n; i++) {
        cout << (uint32_t)sols[i] + 1 << " ";
      }
      cout << "\n";
      checker = 1;
    }
    return ;
  }
  for(int8_t i = 0; i < n; i++) {
    if(!hashes[i] && !getDiag(k, i)) {
      hashes[i] = 1;
      sols[k] = i;
      firstDiags[i + k] = 1;
      secondDiags[i + (n - 1 - k)] = 1;
      generateSolutions(k + 1);
      firstDiags[i + k] = 0;
      secondDiags[i + (n - 1 - k)] = 0;
      hashes[i] = 0;
    }
  }
}

int main() {
	freopen("damesah.in","r",stdin);
	freopen("damesah.out","w",stdout);
  scanf("%d", &n);
  generateSolutions(0);
  cout << total;
}