#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];
inline int getmin(int a,int b){
    if(a<b) return a;
    return b;
}
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(l1-getmin(l1,c1)+1==1)
            poz1=n-(c1-getmin(l1,c1)+1)+1;
         else
            poz1=n+(l1-getmin(l1,c1)+1)-1;
         if(l1-getmin(l1,n-c1+1)+1==1)
            poz2=c1+getmin(l1,n-c1+1)-1;
         else
            poz2=n+(l1-getmin(l1,n-c1+1)+1)-1;
         if(col[c1]==0&&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;
}