#include <bits/stdc++.h>
#define maxim 100
using namespace std;

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

bool col[14],dp[28],ds[28];
int reg[14];
int n,ans;

void bkt(int l)
{
  if (l==n+1)
  {
     ans++;
     if (ans==1)
         for (int i=1; i<=n ;i++)
             g<<reg[i]<<" ";

  }
  else
      for (int c=1;c<=n ;c++)
         if (!col[c] && !ds[l+c]  && !dp[c-l+n])
         {
            reg[l]=c;
            col[c]=ds[l+c]=dp[c-l+n]=1;
            bkt(l+1);
            col[c]=ds[l+c]=dp[c-l+n]=0;
         }


}



int main()
{
    f>>n;
    bkt(1);
    g<<'\n'<<ans;

}