#include <iostream>
#include <fstream>
using namespace std;
ifstream f("damesah.in");
ofstream g("damesah.out");
 int n,sol,use1[100],use2[100],use3[100],s[20];

void Back(int k)
{ int i;
   if (k==n+1) {sol++; if (sol==1) for(i=1;i<=n;i++) g<<s[i]<<" ";}
   else
    for(i=1;i<=n;i++)
    if (!use1[i] && !use2[k+i+50] && !use3[k-i+50])
    { use1[i]=1; use2[k+i+50]=1; use3[k-i+50]=1;
      s[k]=i;
      Back(k+1);
      use1[i]=0; use2[k+i+50]=0; use3[k-i+50]=0;
    }
}

int main()
{
    f>>n;
    Back(1);
    g<<"\n"<<sol;
    return 0;
}