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

using namespace std;

ifstream f ("damesah.in");
ofstream g ("damesah.out");

int n,nrp,d[MAX],atc[MAX],atd1[MAX],atd2[MAX];
void ver (int l){
  if(l==n){
    nrp++;
    if(nrp==1) for(int i=0;i<n;i++)g<<d[i]<<" ";
  } else {
    for(int i=1;i<=n;i++){
      if(!atc[i]&&!atd1[l+i]&&!atd2[i-l+20]){
        atc[i]=atd1[l+i]=atd2[i-l+20]=true;
        d[l]=i;
        ver(l+1);
        atc[i]=atd1[l+i]=atd2[i-l+20]=false;
      }
    }
  }
}

int main()
{
    f>>n;
    ver(0);
    g<<'\n'<<nrp;
    f.close ();
    g.close ();
    return 0;
}