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

using  namespace std;

const int NMAX = 15;
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) {
   if (ix == N) {
      if (!showed) {
         for (int i = 1; i <= N; ++i) {
            printf("%d ", sol[i]);
         }
         showed = true;
         printf("\n");
      }
      total += 1;
      return;
   }

   for (int i = 1; i <= N; ++i) {
      int col_ix = i;
      int nix = ix + 1;
      if (col[col_ix] || diag[col_ix + nix] ||
            antidiag[N + col_ix - nix]) {
         continue;
      }

      sol[nix] = col_ix;

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

      backtrack(nix);

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

   }

}

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

   scanf("%d", &N);

   backtrack(0);

   printf("%d", total);

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