#include <iostream>
#include <fstream>
#define MAX 13

using namespace std;
int n, dame[MAX], first = 1, contor;
ifstream in("damesah.in");
ofstream out("damesah.out");
void afisare()
{
  int i;

  for(i = 0; i < n; i++)out << dame[i] + 1 << " ";
  out << endl;
}
bool validare(int k)
{
  int i;

  for(i = 0; i < k; i++)if(k - i == dame[k] - dame[i] || i - k == dame[k] - dame[i] || dame[i] == dame[k])return 0;
  return 1;
}
void bkt(int k)
{
  int i;

  for(i = 0; i < n; i++)
  {
    dame[k] = i;
    if(validare(k))
    {
      if(k + 1 == n)
      {
        if(first == 1)
        {
          afisare();
          first = 0;
        }
        contor++;
      }
      else bkt(k + 1);
    }
  }
}
int main()
{
  in >> n;
  bkt(0);
  out << contor;
  in.close();
  out.close();
  return 0;
}