#include <fstream>
#include <vector>

using namespace std;

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

int total = 0;

void solve(int n, int curr, vector<int> &sol, vector<bool> &lc, vector<bool> &d1, vector<bool> &d2){
  if(curr > n){
    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;
  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';
}