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

using  namespace std;

const int NMAX = 14;
int N;

vector<bool> col(NMAX, false);
vector<bool> diag(2*NMAX, false);
vector<bool> antidiag(2*NMAX, false);
vector<bool>  row(NMAX, false);
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;
}