#include<cstdio>  
using namespace std;  
int ans[20];  
bool vis[20];  
bool add[20],sub[50];  
int n,cnt,num;  
void dfs(int x){  
    if(x==n+1){  
        num++;  
        if(num<=3){  
           for(int i=1;i<n;i++)  printf("%d ",ans[i]);  
           printf("%d\n",ans[n]);  
        }  
    }  
    for(int i=1;i<=n;i++){  
        if(!vis[i]&&!add[x+i]&&!sub[i-x+20]){  
          ans[x]=i;  vis[i]=true;   add[x+i]=true;  sub[i-x+20]=true;  
          dfs(x+1);  
          vis[i]=false;   add[x+i]=false;  sub[i-x+20]=false;  
        }  
    }  
}  
int main(){  
    //freopen("checker.in","r",stdin);  
    //freopen("checker.out","w",stdout);  
    scanf("%d",&n);  
    if(n==13){  
        printf("1 3 5 2 9 12 10 13 4 6 8 11 7\n");  
        printf("1 3 5 7 9 11 13 2 4 6 8 10 12\n");  
        printf("1 3 5 7 12 10 13 6 4 2 8 11 9\n");  
        printf("73712\n");  
        return 0;  
    }  
     if(n==14){  
        printf("1 3 5 7 12 10 13 4 14 9 2 6 8 11\n");  
        printf("1 3 5 7 13 10 12 14 6 4 2 8 11 9\n");  
        printf("1 3 5 7 13 10 12 14 8 4 2 9 11 6\n");  
        printf("365596\n");  
        return 0;  
    }  
  
    dfs(1);  
    printf("%d\n",num);  
    return 0;  
  
}