#include <fstream>

using namespace std;

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

int nr,n,st[15];
bool col[15],dp[30],ds[30];

int afis(){
  for(int i=1;i<=n;i++) g<<st[i]<<" ";
}

int back(int p){
    if(p>n){ if(!nr) afis();
            nr++;
         }
    else{
     for(int i=1;i<=n;i++){
        st[p]=i;
         if(!col[i] && !dp[n-p+i] && !ds[n-p+i]){
            col[i]=1; dp[n-p+i]=1; ds[n-p+i]=1;
            back(p+1);
            col[i]=0; dp[n-p+i]=0; ds[n-p+i]=0;
            }
       }
    }
}

int main()
{
  f>>n;
  back(1);
  g<<endl<<nr;
  return 0;
}