#include <iostream>
#include <vector>

using namespace std;

int n;
vector<bool> col,deg,indeg;
int cnt = 0;
vector<int> path;

void dfs(int row)
{
  if(row == n+1)
  {
    cnt++;
    if(cnt<=3)
    {
      for(int i = 0;i<n;i++)
      {
        cout<<path[i]<<" \n"[i == n-1];
      }
    }
    return;
  }
  for(int i = 1;i<=n;i++)
  {
    if(!col[i]&&!deg[i+row-1]&&!indeg[row-i+n])
    {
    col[i] = true;
    deg[i+row-1] = true;
    indeg[row-i+n] = true;
    path.push_back(i);
    dfs(row+1);
    col[i] = false;
    deg[i+row-1] = false;
    indeg[row-i+n] = false;
    path.pop_back();
    }
  }
}
int main()
{
  cin>>n;
  col.resize(n,false);
  deg.resize(2*n-1,false);
  indeg.resize(2*n-1,false);
  dfs(1);
  cout<<cnt<< endl;
  return 0;
}