#include <cstdio>
#include <cmath>
using namespace std;
int sol,prima=1,k,n,i,v[15];
int mod(int a)
{
    if(a<0) return -a;
    return a;
}
void afisare()
{
    for(i=1;i<=n;i++)
        printf("%d ",v[i]);
}
int solutie()
{
    if(k==n) return 1;
    return 0;
}
int valid()
{
    for(i=1;i<k;i++)
        if((v[k]==v[i])||(k-i==mod(v[k]-v[i])))
            return 0;
    return 1;
}
int succesor()
{
    if(v[k]<n)
    {
        v[k]++;
        return 1;
    }
    return 0;
}
void back()
{
    int as, ev;
    k=1;v[k]=0;
    while(k)
    {
        do
        {
            as=succesor();
            if(as)
                ev=valid();
        }while(as&&!ev);
        if(as)
            if(solutie())
            {
                if(prima)
                {
                    afisare();
                    prima=0;
                }
                sol++;
            }
            else
            {
                k++;
                v[k]=0;
            }
        else
            k--;
    }
}
int main()
{
    freopen("damesah.in","r",stdin);
    freopen("damesah.out","w",stdout);

    scanf("%d",&n);
    back();
    printf("\n%d",sol);
    return 0;
}