#include <cstdio>
#include <vector>
#include <memory>

using namespace std;

class ChessSolver{
private:
  int boardSize;
  int totalSolutions;
  vector<int> v;
  vector<bool> usedColumn;
  vector<bool> usedMainDiagonal;
  vector<bool> usedSecondaryDiagonal;

  void PrintFirst() {
    for (auto it: v)
      printf("%d ", it + 1);
    printf("\n");
  }

  bool isUsedColumn(int col) {
    return usedColumn[col];
  }
  bool isUsedMainDiagonal(int row, int col) {
    return usedMainDiagonal[row + col];
  }
  bool isUsedSecondaryDiagonal(int row, int col) {
    return usedSecondaryDiagonal[boardSize + row - col - 1];
  }

  void markUsedColumn(int col, bool val) {
    usedColumn[col] = val;
  }
  void markUsedMainDiagonal(int row, int col, bool val) {
    usedMainDiagonal[row + col] = val;
  }
  void markUsedSecondaryDiagonal(int row, int col, bool val) {
    usedSecondaryDiagonal[boardSize + row - col - 1] = val;
  }
  
  void backtrack(int k) {
    for (v[k] = 0; v[k] < boardSize; ++v[k])
      if (!isUsedColumn(v[k]) &&
	  !isUsedMainDiagonal(k, v[k]) &&
	  !isUsedSecondaryDiagonal(k, v[k])) {

	if (k == boardSize - 1) {
	  ++totalSolutions;
	  if (totalSolutions == 1)
	    PrintFirst();
	}
	else {
	  markUsedColumn(v[k], true);
	  markUsedMainDiagonal(k, v[k], true);
	  markUsedSecondaryDiagonal(k, v[k], true);

	  backtrack(k + 1);

	  markUsedColumn(v[k], false);
	  markUsedMainDiagonal(k, v[k], false);
	  markUsedSecondaryDiagonal(k, v[k], false);
	}
      }
  }
  
public:
  void execute(int _boardSize) {
    boardSize = _boardSize;
    totalSolutions = 0;
    v.resize(boardSize);
    usedColumn.resize(boardSize);
    usedMainDiagonal.resize(2 * boardSize - 1);
    usedSecondaryDiagonal.resize(2 * boardSize - 1);

    backtrack(0);
  }
  int getNumberSolutions() {
    return totalSolutions;
  }
};

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

  int N;
  scanf("%d", &N);
  
  unique_ptr<ChessSolver> s = make_unique<ChessSolver>();
  s->execute(N);
  printf("%d\n", s->getNumberSolutions());
}