#include <fstream>
#include <cmath>
using namespace std;

ifstream fin ("damesah.in");
ofstream fout ("damesah.out");

int n, i, c, p, k, x, t[15];

int main()
{
  fin >> n;
  k = 1; t[k] = 0;
  while (k){
    do{
      p = c = 0;
      if (t[k] < n){
        p = 1;
        t[k] ++;
      }
      for (i = 1; i < k; i ++){
        if (t[i] == t[k] || abs(i - k) == abs(t[i] - t[k])) c ++;
        if (c) break;
      }
    } while (p && c);
    if (k == n && p && !c){
      x ++;
      if (x == 1){
        for (i = 1; i <=n; i ++)
           fout << t[i] << " ";
        fout << '\n';
      }
    } else
    if (k < n && p && !c){
      k ++;
      t[k] = 0;
    } else k --;
  }
  fout << x;
  return 0;
}