#include<fstream>
using namespace std;
ifstream f("damesah.in");
ofstream g("damesah.out");
int n,p[14],sol;
bool c[14],dp[27],dm[27];
void back(int i)
{
    for(int j=1;j<=n;++j)
      if(!c[j]&&!dp[i+j]&&!dm[i-j+n])
      {
          p[i]=j;
          c[j]=dp[i+j]=dm[i-j+n]=1;
          if(i==n&&!sol++)
            for(int k=1;k<=n;++k)
              g<<p[k]<<" ";
          else
            back(i+1);
          c[j]=dp[i+j]=dm[i-j+n]=0;
      }
}
int main()
{
    f>>n;
    back(1);
    g<<"n"<<sol;
    return 0;
}