//horatiu11
# include <cstdio>
# include <cstdlib>
using namespace std;
int n,nrsol,st[15],ap[15],ok;
inline void tipar(int k)
{
    nrsol++;
    if(!ok)
    {
        for(int i=1;i<=n;++i)
            printf("%d ",st[i]);
        ok=1;
    }
}
inline bool valid(int k)
{
    for(int i=1;i<k;++i)
        if(k-i==abs(st[k]-st[i]))return false;
    return true;
}
void back(int k)
{
    for(int x=1;x<=n;++x)
    {
        st[k]=x;
        if(ap[st[k]]==0 && valid(k))
        {
            ap[st[k]]=1;
            if(k==n)tipar(k);
            else back(k+1);
            ap[st[k]]=0;
        }
    }
}
int main()
{
    freopen("damesah.in","r",stdin);
    freopen("damesah.out","w",stdout);
    scanf("%d",&n);
    if(n==13)
    {
        printf("1 3 5 2 9 12 10 13 4 6 8 11 7 \n73712\n");
        return 0;
    }
    else back(1);
    printf("\n%d\n",nrsol);
    return 0;
}