#include<bits/stdc++.h>

using namespace std;

#define ll long long

bool cused[];

bool zxused[];

bool yxused[];

//bool g[14][14];

int ans[];

int atop=;

int n;

int cnt=;

inline int get_zx_id(int r,int c){

    //int ans=r-c+n;

    //printf("r=%d c=%d zid=%d\n",r,c,ans);

    return r-c+n;

}

inline int get_yx_id(int r,int c){

    int rc=n+-c;

    //int ans=r-rc+n;

    //printf("r=%d c=%d yid=%d\n",r,c,ans);

    return r-rc+n;

}

void dfs(int r){

    if(r>n){

        cnt++;

        if(cnt<=){

            for(int i=;i<atop;i++){

                printf("%d%c",ans[i]," \n"[i==atop-]);

            }

        }

    }

    for(int j=;j<=n;j++){

        if(cused[j]==&&zxused[get_zx_id(r,j)]==&&yxused[get_yx_id(r,j)]==){

            cused[j]=;

            zxused[get_zx_id(r,j)]=;

            yxused[get_yx_id(r,j)]=;

            //g[r][j]=1;

            //ans[atop++]=r;

            ans[atop++]=j;

            dfs(r+);

            atop-=;

            //g[r][j]=0;

            zxused[get_zx_id(r,j)]=;

            yxused[get_yx_id(r,j)]=;

            cused[j]=;

        }

    }

}

int main(){

    scanf("%d",&n);

    /*for(int i=1;i<=n;i++){

        for(int j=1;j<=n;j++){

            printf("%2d ",get_zx_id(i,j));

        }

        printf("\n");

    }

    printf("\n");

    for(int i=1;i<=n;i++){

        for(int j=1;j<=n;j++){

            printf("%2d ",get_yx_id(i,j));

        }

        printf("\n");

    }

    printf("\n");*/

    int r=;

    for(int j=;j<=n;j++){

        cused[j]=;

        zxused[get_zx_id(r,j)]=;

        yxused[get_yx_id(r,j)]=;

        ans[atop++]=j;

        dfs(r+);

        atop-=;

        yxused[get_yx_id(r,j)]=;

        zxused[get_zx_id(r,j)]=;

        cused[j]=;

    }

    printf("%d\n",cnt);

}