#include <stdio.h>

using namespace std;

FILE*f=fopen("damesah.in","r");
FILE*g=fopen("damesah.out","w");

int t,n;
int l[15],dp[30],ds[30],q[15];

void bck(int c){
    int i;
    if (c==n+1){
        if (t==0){
            for (i=1;i<=n;i++) fprintf(g,"%d ",q[i]);
        }
        t++;
        return;
    }
    for (i=1;i<=n;i++)
        if (!l[i]&&!dp[i-c+n]&&!ds[i+c]){
            l[i]=1;
            dp[i-c+n]=1;
            ds[i+c]=1;
            q[c]=i;
            bck(c+1);
            l[i]=0;
            dp[i-c+n]=0;
            ds[i+c]=0;
        }
}

int main()
{
    fscanf(f,"%d",&n);
    bck(1);
    fprintf(g,"\n%d\n",t);
    fclose(f);
    fclose(g);
    return 0;
}