#include <bits/stdc++.h>
#define DM 50
using namespace std;
FILE *fin=fopen("damesah.in","r");
FILE *fout=fopen("damesah.out","w");
bitset<DM>lin,d1,d2;
int v[DM],n,cont;
bool ok=0;

void afis(){
    for(int i=1;i<=n;++i) fprintf(fout,"%d ",v[i]);
}

void bck(int step){
    if(step==n+1){
        cont++;
        if(!ok) afis(),ok=1;
        return;
    }
    for(int i=1;i<=n;++i){
        if(!lin[i] && !d1[step+i] && !d2[step-i+n]){
            lin[i]=1;
            d1[step+i]=1;
            d2[step-i+n]=1;
            v[step]=i;
            bck(step+1);
            lin[i]=0;
            d1[step+i]=0;
            d2[step-i+n]=0;
        }
    }
}

int main()
{
    fscanf(fin,"%d",&n);
    bck(1);
    fprintf(fout,"\n%d",cont);
    return 0;
}