#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;

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

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

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

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

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

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

}

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;
}