#include <fstream>

using namespace std;

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

int n, ans;

int v[15], sol[15];
bool c[15], d[2][35];

void bkt(int niv) {
  if(niv == n + 1) {
    ans++;
    if(ans == 1) {
      for(int i = 1; i <= n; i++)
        sol[i] = v[i];
    }
    return;
  }
  for(int i = 1; i <= n; i++) {
    if(!c[i] && !d[0][i - niv + n] && !d[1][i + niv]) {
      c[i] = d[0][i - niv + n] = d[1][niv + i] = 1;
      v[niv] = i;
      bkt(niv + 1);
      c[i] = d[0][i - niv + n] = d[1][i + niv] = 0;
    }
  }
}

int main() {
  cin >> n;
  bkt(1);
  for(int i = 1; i <= n; i++)
    cout << sol[i] << " ";
  cout << "\n" << ans;
  return 0;
}