#include <cstdio>
#include <cmath>
#define MAXN 14
using namespace std;
int sol[MAXN],n,co;
bool ok=false,col[MAXN+1],diag[2*MAXN+1],diag2[2*MAXN+1];
FILE *fin,*fout;
inline bool valid(int k,int i)
{
    return !col[i] && !diag[k-i+n-1] && !diag2[k+i];
}
inline void write()
{
    for(int i=1;i<=n;i++)
        fprintf(fout,"%d ",sol[i]);
}
void back(int k)
{
    if(k==n+1)
    {
        if(!ok)
        {
            write();
            ok=true;
        }
        co++;
    }
    else
        for(int i=1;i<=n;i++)
            if(valid(k,i))
            {
                sol[k]=i;
                col[i]=true;diag[k-i+n-1]=true;diag2[k+i]=true;
                back(k+1);
                col[i]=false;diag[k-i+n-1]=false;diag2[k+i]=false;
            }
}
int main()
{
    fin=fopen("damesah.in","r");
    fout=fopen("damesah.out","w");
    fscanf(fin,"%d",&n);
    back(1);
    fprintf(fout,"\n%d",co);
    fclose(fin);
    fclose(fout);
    return 0;
}