#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
int st[20],sol=0,n,viz[20],d1[40],d2[40];
void backt(int k)
{
    int i;
    if(k==n+1)
    {
        sol++;
        if(sol==1)
          for(i=1;i<=n;++i)
            printf("%d ",st[i]);
    }
    else
    {
        for(i=1;i<=n;i++)
            if(viz[i]==false&&d1[k+i]==false&&d2[k-i+n]==false)
            {
                viz[i]=true;
                d1[k+i]=true;
                d2[k-i+n]=true;
                st[k]=i;
                backt(k+1);
                st[k]=0;
                viz[i]=false;
                d1[k+i]=false;
                d2[k-i+n]=false;
            }
    }
}
int main()
{
    freopen("damesah.in","r",stdin);
    freopen("damesah.out","w",stdout);
    scanf("%d",&n);
    backt(1);
    printf("\n%d",sol);
}