#include<cstdio>
#include<vector>
#include<cstring>

using namespace std;

const int MAXN=30;

int nr,n;
bool found;
vector<int> sl,ans;

bool col[MAXN],dip[MAXN],dis[MAXN];

void find_sol(int i){
    if(i>n){
        ans=sl;
        found=true;
        return;
    }

    for(int j=1;j<=n && !found;j++){
        int di1,di2;
        di1=n+j-i;
        di2=2*n-j-i;

        if(!col[j] && !dip[di1] && !dis[di2]){
            col[j]=true;
            dip[di1]=true;
            dis[di2]=true;
            sl.push_back(j);
            find_sol(i+1);
            sl.pop_back();
            col[j]=false;
            dip[di1]=false;
            dis[di2]=false;
        }
    }

    return;
}

void bktr(int i){
    if(i>n){
        nr++;
        return;
    }

    for(int j=1;j<=n;j++){
        int di1,di2;
        di1=n+j-i;
        di2=2*n-j-i;

        if(!col[j] && !dip[di1] && !dis[di2]){
            col[j]=true;
            dip[di1]=true;
            dis[di2]=true;
            bktr(i+1);
            col[j]=false;
            dip[di1]=false;
            dis[di2]=false;
        }
    }

    return;
}

int main(){
    freopen("damesah.in","r",stdin);
    freopen("damesah.out","w",stdout);

    scanf("%d",&n);

    find_sol(1);
    memset(col,0,sizeof(col));
    memset(dip,0,sizeof(dip));
    memset(dis,0,sizeof(dis));

    bktr(1);

    for(unsigned j=0;j<ans.size();j++){
        printf("%d ",ans[j]);
    }
    printf("\n%d",nr);

    return 0;
}