#include <fstream>
#include <algorithm>

using namespace std;

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

#define DIM 15

int n, total;
int fr[DIM + 1], sol[DIM + 1], ans[DIM + 1];

static inline int modul(int x) {
  return (x < 0 ? -x : x);
}

//sa nu fie pe diagonala;a
static inline bool Check(int k) {
  int i = 1;
  while(i < k && modul(i - k) != modul(sol[i] - sol[k]))  
    i++;
  return (i == k);
}

static inline void Solutie() {
  if(total == 0)
    for(int i = 1; i <= n; i++)
      ans[i] = sol[i];
  total++;
}

static inline void Back(int k) {
  if(k > n)
    Solutie();
  else for(int i = 1; i <= n; i++) {
    sol[k] = i;     //pozitia pe care l pun pe i;
    fr[i]++;        //sa nu am mai multe elemente pe coloana i;
    if(fr[i] == 1 && Check(k))
      Back(k + 1);
    fr[i]--;
  }
}

int main() {
  fin >> n;

  total = 0;
  Back(1);

  for(int i = 1; i <= n; i++)
    fout << ans[i] << " ";
  fout << '\n' << total;

  return 0;
}