#include<stdio.h>
#include<stdlib.h>
int st[14],n,k,nr=0,prima=0;
void Init()
	 { st[k]=0; }
int Am_Succesor()
	{ if (st[k]<n)
		{ st[k]++;
			return 1;
			}
		else return 0;
	}
int E_valid() {
	for( int i=1;i<k;i++)
		if(st[i]==st[k] || abs(st[k]-st[i])==abs(k-i)) return 0;
	return 1;
}
int Solutie()
{ return k==n; }
void Tipar() {
	for (int i=1;i<=n;i++)
			printf("%d ",st[i]);
		printf("\n");
}
void back() {
	int AS;
	k=1;Init();
		while( k>0)
		{ do {} while((AS=Am_Succesor()) && !E_valid());
		if (AS)
			if (Solutie()){
					nr++;
			if(prima==0) { Tipar(); prima=1; }
			}
			else { k++;Init(); }
		else k--;
		}
}
int main() {
	freopen("damesah.in","r",stdin);
	freopen("damesah.out","w",stdout);
	scanf("%d",&n);
	back();
	printf("%d",nr);
	fclose(stdin);
	fclose(stdout);
	return 0;
	}