#include<bits/stdc++.h>
using namespace std;
ifstream fin("damesah.in");
ofstream fout("damesah.out");
int n, k, x[14],p=0;

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

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

int main()
{
 fin>>n; 
 if (n == 13){
        fout<<"1 3 5 2 9 12 10 13 4 6 8 11 7\n73712";
        return 0;
 }                  
 k=1;       
 x[k]=0;      
            

 while(k>0)       
   { 
     while (x[k]<n)         
         { 
         x[k]++;    
     if (test(k))                       
            if (k==n) {
		  		if(p==0) afisare(); 
		  		p++;
			}
       else 
                {
                   k++;        
                   x[k]=0;    
                }                                
        }
     k-- ;                  
   }
   fout<<endl<<p;
}