#include<fstream>
using namespace std;
int i,j,nr,st[15],lev,n,sol[15];
bool ok=1;

int abs(int x) { if (x<0) return(-x); else return(x); }

void back(int lev) {
     if (lev>n) {
                ++nr;
                if (ok) {
                        ok=0;
                        for (int i=1; i<=n; ++i) sol[i]=st[i];
                        }
                }
     else for (int i=st[lev]+1; i<=n; ++i) {
            
            bool aux=1;
            for (int j=1; j<lev; ++j) 
             if ( st[j]==i || ( abs(st[j]-i)==lev-j) ) { aux=0; break; }
            if (aux) { st[lev]=i; back(lev+1); st[lev]=0; }
            
            }
            
}

int main(void) {
    ifstream fin("damesah.in");
    ofstream fout("damesah.out");
    fin>>n;
    
    back(1);
    
    for (i=1; i<=n; ++i) fout<<sol[i]<<" ";
    fout<<"\n"<<nr;
  return(0);
}