#include <fstream>
#include <cmath>

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

int x[11],viz[11],n;
int ct;

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

void afisare()
{ int i,j;
  for(i=1; i<=n; i++)
      fout<<x[i]<<" ";
}

void Back(int k)
{ int i;
  for(i=1; i<=n; i++)
      if(viz[i]==0)
        { x[k]=i;
          viz[i]=1;
          if(valid(k))
             if(k==n)
                {
                    ct++;
                    if(ct==1)
                        for(int j=1; j<=n; j++) fout<<x[j]<<" ";
                }
             else Back(k+1);
          viz[i]=0;
        }
}

int main()
{ fin>>n;
  Back(1);
  fout<<"\n"<<ct;
  return 0;
}