#include <iostream>
#include <fstream>
#include <cmath>

using namespace std;

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

int n,st[14],viz[14],nr,ok ;

void Afisare()
{
    int i ;
    if(ok==0) for(i=1;i<=n;i++) {g<<st[i]<<" " ;
                                 ok=1 ;
    }
    nr++ ;

}

int valid(int top,int x)
{
    int i ;
    if(viz[x]==1) return 0 ;
    for(i=1;i<top;i++)
        if(abs(top-i)==abs(x-st[i])) return 0 ;
    return 1 ;
}

void backt(int top )
{
    int i ;
    if(top==n+1) Afisare() ;
      else for(i=1;i<=n;i++)
                if(valid(top,i))
      {
          viz[i]=1 ;
          st[top]=i ;
          backt(top+1) ;
          viz[i]=0 ;

      }

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

}