#include <bits/stdc++.h>
/// TONI BO$$ was here
/// #MLC

using namespace std;

int v[15],f[15],nr,n,j;
void bkt(int i)
{
    if(i>n)
    {
        if(nr==0)
            for(j=1; j<=n; j++)
                printf("%d ",v[j]);
        nr++;
        return ;
    }
    for(v[i]=1; v[i]<=n; v[i]++)
        if(!f[v[i]])
        {
            for(j=1; j<i; j++)
                if(i-j==abs(v[i]-v[j]))
                    break;
            if(j==i)
            {
                f[v[i]]=1;
                bkt(i+1);
                f[v[i]]=0;
            }
        }
}

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

    return 0;
}