#include <stdio.h>
#include <stdlib.h>

#define D 1
#define MAXN 13
int max[MAXN];
int line[MAXN];
int column[MAXN];
int diagonalRL[MAXN*2];
int diagonalLR[MAXN*2];

int answer[MAXN];
int saveAnswer[MAXN];

int maxN;
int apMax;
int n;


void nextPoz(int depth, int l){
  int c, i;

  if(l == n){
    if(depth > maxN){
      maxN = depth;
      apMax = 1;

      for(i = 0; i < depth; i++)
        saveAnswer[i] = answer[i];

    }else if(depth == maxN)
      apMax++;
  }

  for(c = 0; c < n; c++){
    if(column[c] + diagonalLR[l+c]+diagonalRL[2*n-l+c-1] == 0){
      line[l] = 1;
      column[c] = 1;
      diagonalLR[l+c] = 1;
      diagonalRL[2*n-l+c-1] = 1;

      answer[depth] = c;
      nextPoz(depth+1, l+1);

      line[l] = 0;
      column[c] = 0;
      diagonalLR[l+c] = 0;
      diagonalRL[2*n-l+c-1] = 0;
    }
  }

}

int main()
{
    FILE *in, *out;
    int i;

    in = fopen("damesah.in", "r");
    fscanf(in, "%d", &n);
    fclose(in);

    maxN = 0;
    nextPoz(0, 0);

    out = fopen("damesah.out", "w");
    for(i = 0; i < maxN; i++)
      fprintf(out, "%d ", saveAnswer[i]+1);
    fprintf(out, "\n%d\n", apMax);
    fclose(out);

    return 0;
}