#include <iostream>
#include <fstream>
#define nmax 15
using namespace std;
ifstream fin("damesah.in");
ofstream fout("damesah.out");
int x[nmax],n; ///back
bool viz[nmax],ds[nmax],dp[nmax];
int nr; ///nr sol

void Write()
{int i;
 for(i=1;i<=n;i++)
    fout<<x[i]<<" ";
 fout<<endl;
}

void Back(int k)
{int i;
 for(i=1;i<=n;i++)
    {x[k]=i;
     if(viz[i]==0&&ds[k+i-1]==0&&dp[n-k+i]==0)
      {viz[i]=ds[k+i-1]=dp[n-k+i]=1;
       if(k==n)
         {nr++;
          if(nr==1) Write();
          }
        else Back(k+1);
       viz[i]=ds[k+i-1]=dp[n-k+i]=0;
       }
    }
}

int main()
{fin>>n;
 Back(1);
 fout<<nr<<endl;
 return 0;
}