#include <iostream>
#include <fstream>
using namespace std;
int v[15],l[30],d1[50],d2[50],k,n,s,nr,i;
ifstream in("damesah.in");
ofstream out("damesah.out");
bool verif(int k)
{
    if (l[v[k]]==0&&d1[k-v[k]+n]==0&&d2[k+v[k]]==0&&v[k]>0) return true;
    return false;
}
int main()
{
    in>>n;
    k=1;
    while (k>0)
    {
        if (v[k]!=0) {l[v[k]]=0;d1[k-v[k]+n]=0;d2[k+v[k]]=0;}
        v[k]++;
        while (v[k]<=n&&(!verif(k))) v[k]++;
        if (v[k]>n) {k--;}
        else
        {
            l[v[k]]=1;
            d1[k-v[k]+n]=1;
            d2[k+v[k]]=1;
            if (k==n)
            {
                nr++;
                if (s==0) {for (i=1;i<=n;i++) out<<v[i]<<" ";out<<endl;s=1;}

            }
            else
            {
                k++;v[k]=0;
            }
        }
        //for (i=1;i<=n;i++) cout<<v[i]<<" ";cout<<endl;
    }
    out<<nr;
}