#include <cstdio>

using namespace std;
int n,m,a,v[15],c[15],P[50],s[50],*p;
void back(int);
int main()
{
    freopen("damesah.in","r",stdin);
    freopen("damesah.out","w",stdout);
    p=P+25;scanf("%d",&n);back(1);printf("%d\n",m);
    return 0;
}
void back(int i)
{
    int j;
    if(i==n+1)
    {
        m++;
        if(a)return;
        a=1;
        for(j=1;j<n;j++)printf("%d ",c[j]);printf("%d\n",c[j]);
        return;
    }
    for(j=1;j<=n;j++)
        if(!(v[j]+p[i-j]+s[i+j]))
           {
               v[j]++;p[i-j]++;s[i+j]++;c[i]=j;
               back(i+1);
               v[j]--;p[i-j]--;s[i+j]--;c[i]=0;
           }
}