/*
  NAME : Nursoltan
  PROB : checker
  LANG : C++
  DATE : 03/07/11 20:40
*/
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <sstream>
#include <iostream>
#include <map>
#include <set>
#include <stack>
#include <utility>
#include <queue>
 
using namespace std;
 
#define MAX 100
#define INF INT_MAX
#define eps (1e-9)
 
#define FOR(_i,_k,_n) for(int (_i)=(_k); (_i)<(_n); (_i)++)
#define FORR(_i,_k,_n) for(int (_i)=(_k); (_i)>=(_n); (_i)--)
#define CLR(_x) memset((_x),0,sizeof(_x))
#define SQR(_x) ((_x)*(_x))
#define all(_x) _x.begin(),_x.end()
#define sz(_x) sizeof(_x)
 
#define vc vector<int>
#define pb push_back
#define mp make_pair
#define iss istringstream
#define oss ostringstream
#define px first
#define py second
 
typedef long long ll;
typedef pair <int,int> point;
int ABS(int _x){ return _x>0?_x:-_x; }
 
int N,shiid[20],cnt;
int VIS,RDIA,LDIA;
 
void rec(int row){
     if(row==N){
       if(cnt<3){
         FOR(i,0,N){ if(i>0) cout<<" "; cout<<shiid[i]+1; }
         cout<<endl;
       }
       cnt++;
     }
     else
       FOR(col,0,N)
         if(!(VIS & 1<<col) && !(RDIA & 1<<(col-row+N)) && !(LDIA & 1<<(col+row))){
           VIS|=1<<col;
           RDIA|=1<<(col-row+N);
           LDIA|=1<<(col+row);
           shiid[row]=col;
           rec(row+1);
           VIS&=~(1<<col);
           RDIA&=~(1<<(col-row+N));
           LDIA&=~(1<<(col+row));
         }
}
 
int main()
{
    freopen("checker.in","r",stdin);
    freopen("checker.out","w",stdout);
 
    cin>>N;
    rec(0);
    cout<<cnt<<endl;
 
    //system("pause");
    return 0;
}