#include <stdio.h>
FILE *f1,*f2;
int n,k,s,st[15];

int mod(int x)
{
    if(x<0)
        x=-x;
    return x;
}
bool am_succesor()
{
    if(st[k]<n)
    {
        st[k]++;
        return true;
    }
    return false;
}
bool valid()
{
    for(int i=1;i<k;i++)
        if(st[i]==st[k] || mod(st[k]-st[i])==k-i)
            return false;
    return true;
}
void sol()
{
    s++;
    if(s==1)
    {
        for(int i=1;i<=n;i++)
            fprintf(f2,"%d ",st[i]);
        fprintf(f2,"\n");
    }
}
void back()
{
    bool as;
    k=1;st[1]=0;
    while(k>0)
    {
        do{}while((as=am_succesor())&& !valid());
        if(as)
            if(k==n)
                sol();
            else
            {
                k++;
                st[k]=0;
            }
        else k--;
    }
}


int main()
{
    f1=fopen("damesah.in","r");
    f2=fopen("damesah.out","w");
    fscanf(f1,"%d",&n);
    back();
    fprintf(f2,"%d",s);
    return 0;
}