#include <stdio.h>
#include <vector>

using  namespace std;

const int NMAX = 14;

int N;

bool col[NMAX];
bool diag[2*NMAX+1];
bool antidiag[2*NMAX+1];
bool  row[NMAX];
vector<int> sol(NMAX, -1);

bool showed = false;
int total = 0;

void backtrack(int ix, int col_ix) {
   if (col[col_ix] || diag[col_ix + ix] ||
	 antidiag[N + col_ix - ix]) {
      return;
   }
   sol[ix] = col_ix;

   if (ix == N) {
      if (!showed) {
	 for (int i = 1; i <= N; ++i) {
	    printf("%d ", sol[i]);
	 }
	 showed = true;
	 printf("\n");
      }
      total += 1;
      return;
   }

   col[col_ix] = true;
   diag[col_ix + ix] = true;
   antidiag[N + col_ix - ix] = true;

   for (int i = 1; i <= N; ++i) {
      backtrack(ix + 1, i);
   }

   col[col_ix] = false;
   diag[col_ix + ix] = false;
   antidiag[N + col_ix - ix] = false;
}

int main() {
   freopen("damesah.in", "r", stdin);
   freopen("damesah.out", "w", stdout);

   scanf("%d", &N);

   for (int i = 1; i <= N; ++i) {
      backtrack(1, i);
   }

   printf("%d", total);

   fclose(stdin);
   fclose(stdout);
   return 0;
}