#include <cstdio>
#define MAXN 13
char col[MAXN+1],d1[2*MAXN+1],d2[2*MAXN+1];
int ans=0;
char c[MAXN+1],rez[MAXN+1];
int n;
void bkt(int l1){
    int i,c1,poz1,poz2;
    if(l1==n+1){
       ans++;
       if(ans==1)
          for(i=1;i<=n;i++)
            rez[i]=c[i];
    }
    else
      for(c1=1;c1<=n;c1++)
         if(col[c1]==0){
            poz1=n+c1-l1;
            poz2=l1+c1+1;
            if(d1[poz1]==0&&d2[poz2]==0){
              c[l1]=c1;
              col[c1]=1;
              d1[poz1]=1;
              d2[poz2]=1;
              bkt(l1+1);
              col[c1]=0;
              d1[poz1]=0;
              d2[poz2]=0;
            }
         }
}
int main(){
   FILE*fi,*fout;
   int i;
   fi=fopen("damesah.in" ,"r");
   fout=fopen("damesah.out" ,"w");
   fscanf(fi,"%d" ,&n);
   bkt(1);
   for(i=1;i<=n;i++)
     fprintf(fout,"%d " ,rez[i]);
   fprintf(fout,"\n%d" ,ans);
   fclose(fi);
   fclose(fout);
   return 0;
}