#include <fstream>
using namespace std;
ifstream in("damesah.in");
ofstream out("damesah.out");
int afis[14],v[14],col[14],st[27],dr[27],cnt,n;
void bkt(int poz)
{
 int i;
 if(poz==n)
 {
  if(afis[1]==0)
        for(i=1;i<=poz;i++)
        afis[i]=v[i];
  else{
    for(i=1;i<=n;i++)
        if(afis[i]!=v[i])
        break;
    if(i!=n+1&&v[i]<afis[i])
        for(i=1;i<=n;i++)
        afis[i]=v[i];
  }
  cnt++;
 }
 for(i=1;i<=n;i++)
 {
  if(col[i]==0&&dr[poz+i]==0&&st[poz-i+13]==0)
  {
   col[i]=dr[poz+i]=st[poz-i+13]=1;
   v[poz+1]=i;
   bkt(poz+1);
   v[poz+1]=0;
   col[i]=dr[poz+i]=st[poz-i+13]=0;
  }
 }
}
int main()
{
    in>>n;
    bkt(0);
    for(int i=1;i<=n;i++)
        out<<afis[i]<<" ";
    out<<'\n'<<cnt;
    return 0;
}