#include <algorithm>
#include <string>
#include <iostream>
#include <cstdio>
#include <vector>
#include <set>
#include <map>
#include <queue>
using namespace std;

#ifdef INFOARENA
#define TEST 0
#else
#define TEST 1
#endif

int sol_counter = 0;
vector<int> first_sol;

bool IsValid(const vector<int> &config, int step, int j) {
  for (int i = 0; i < step; ++i) {
    if (config[i] == j ||
        config[i] == j + (step - i) ||
        config[i] == j - (step - i)) {
      return false;
    }
  }
  return true;
}

void BackTrack(vector<int> &config, int n, int step) {
  if (step == n) {
    sol_counter++;
    if (sol_counter == 1) {
      first_sol = config;
    }
  }
  for (int j = 1; j <= n; ++j) {
    if (IsValid(config, step, j)) {
      config[step] = j;
      BackTrack(config, n, step + 1);
    }
  }
}

int main() {
  freopen("damesah.in","r",stdin);
  freopen("damesah.out","w",stdout);
  int n;
  scanf("%d", &n);
  vector<int> config(n, 0);
  BackTrack(config, n, 0);
  for (int col : first_sol) {
    printf("%d ", col);
  }
  printf("\n");
  printf("%d\n", sol_counter);

  return 0;
}