#include <stdio.h>
using namespace std;
int n, sol[20], lin, ok, nr, ii;
int d2[20], d1[20], col[20];

void backt(int lin)
{
    if(lin==n+1)
        for(++ok; ok<=1 && ii<n; printf("%d ", sol[++ii]));
    else
        for(int i=1; i<=n; ++i)
            if(!d1[lin+i-1] && !d2[lin-i+n] && !col[i])
            {
                sol[lin]=i;
                d1[lin+i-1]=1;
                d2[lin-i+n]=1;
                col[i]=1;
                backt(lin+1);
                d1[lin+i-1]=0;
                d2[lin-i+n]=0;
                col[i]=0;
            }
}

int main()
{
    freopen("damesah.in", "r", stdin);
    freopen("damesah.out", "w", stdout);
    scanf("%d", &n);
    backt(1);
    printf("\n%d", ok);
    return 0;
}