#include<cstdio>
#include<bitset>
using namespace std;
const int NMAX = 15;
int N,St[NMAX],Sol;
bitset<NMAX> C,DP,DS;
void Back(int l)
{
    if(l==N+1)
    {
        if(!Sol++)
        {
            for(int c=1;c<=N;c++) printf("%d ",St[c]);
            printf("\n");
        }
    }
    for(int c=1;c<=N;c++)
        if(!C[c] && !DP[l-c+N] && !DS[l+c])
        {
            St[l]=c;
            C[c]=DP[l-c+N]=DS[l+c]=1;
            Back(l+1);
            C[c]=DP[l-c+N]=DS[l+c]=0;
        }
}
int main()
{
	freopen("damesah.in","r",stdin);
	freopen("damesah.out","w",stdout);
	scanf("%d",&N); Back(1); printf("%d\n",Sol);
	return 0;
}