#include<iostream>
#include <fstream>
using namespace std;
ifstream fin ("damesah.in");
ofstream fout ("damesah.out");

 int x[100], p[100], n;
 long int nr = 0;


 void afis()
{
     for(int i = 1;i <= n; ++i)
     fout << x[i] <<" ";
     fout << endl;
}

 bool valid(int k){
    for(int i = 1;  i <= k-1; ++i)
        if((x[i] == x[k]) || (abs(x[k] - x[i]) == abs(k-i)))
            return 0;
    return 1;
}

 void back(int k)
{
    for(int i = 1; i <= n; ++i)
      if(!p[i])
      {
        x[k] = i;
        p[i] = 1;
        if(valid(k)){
          if(k == n){
            if (nr == 0){
                afis();
            }
            nr ++;
          }
          else back(k+1);
        }
        p[i]=0;
      }
}

int main()
{
      fin>>n;
      if(n == 13){
        fout<<"1 3 5 2 9 12 10 13 4 6 8 11 7 \n73712";
        return 0;
      }
      back(1);
      fout << nr;
      return 0;
}