#include <fstream>

using namespace std;

ifstream fin("damesah.in");
ofstream fout("damesah.out");

short n,v[13],l[13],d1[27],d2[27],i,j[13];
int s;

int main()
{
    fin>>n;
    loop1:;
    if(i==n)
    {
        if(s==0)
        {
            short a=0;
            loop4:;
            if(a<n)
            {
                fout<<v[a]+1<<" ";
                ++a;
                goto loop4;
            }
        }
        s++;
        goto loop2;
    }
    else
    {
        j[i]=0;
        loop3:;
        if(j[i]<n)
        {
            if(l[j[i]]==0 && d1[j[i]-i+n-1]==0 && d2[j[i]+i]==0)
            {
                v[i]=j[i];
                l[j[i]]=1;
                d1[j[i]-i+n-1]=1;
                d2[j[i]+i]=1;
                i++;
                goto loop1;
                loop2:;
                --i;
                l[j[i]]=0;
                d1[j[i]-i+n-1]=0;
                d2[j[i]+i]=0;
            }
            j[i]++;
            goto loop3;
        }
        if(i)
            goto loop2;
    }
    fout<<"\n"<<s;
}