#include <bits/stdc++.h>

const int MAXN=15;
int ans=0,n,queen[MAXN];
bool col[MAXN],main_diag[2*MAXN],sec_diag[2*MAXN];

void bkt(int l, int n)
{
    int c;
    if (l==n+1)
    {
        if (ans<1)
            for (c=1; c<=n; c++)
                printf("%d ",queen[c]);
        ans++;
    }
    else
        for (c = 1; c <= n; c++ )
            if (!col[c] && !main_diag[c-l+n-1] && !sec_diag[l+c])
            {
                queen[l]=c;
                col[c]=main_diag[c-l+n-1]=sec_diag[l+c]=true;
                bkt(l+1,n);
                col[c]=main_diag[c-l+n-1]=sec_diag[l+c]=false;
            }
}

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