#include <bits/stdc++.h>

using namespace std;

int n,sol,v[15];
bitset<30> col,mdiag,sdiag;

void backk(int poz)
{
    if(poz==n+1)
    {
        if(sol==0)
            for(int i=1;i<=n;i++) printf("%d ",v[i]);
        sol++;
        return;
    }
    else
    {
        for(int i=1;i<=n;i++)
            if(!col[i] && !mdiag[i-poz+n] && !sdiag[i+poz])
            {
                v[poz]=i;
                col[i]=mdiag[i-poz+n]=sdiag[i+poz]=1;
                backk(poz+1);
                col[i]=mdiag[i-poz+n]=sdiag[i+poz]=0;
            }
    }
}

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