#include <iostream>
#include <algorithm>
#include <fstream>


using namespace std;

ifstream fcin("damesah.in");
ofstream fcout("damesah.out");

const int NLIM = 1000;

int N;

int xx[NLIM];

int ds[NLIM];
int dd[NLIM];

int v[NLIM];


int res = 0;

void f( int d )
{
	if( d == N )
	{
		++res;

		if(res == 1 )
		{
			for( int i = 0; i < N; ++i )
				fcout << v[i] + 1 << " ";
			fcout << "\n";
		}
	}
	for( int i = 0; i < N; ++i ) 
	{
		int add = 30;
		if( !xx[i] && !ds[d + i] && !dd[ d - i + add ] ) 
		{
			v[d] = i;
			xx[i] = 1;
			ds[d + i] = 1;
			dd[ d - i + add] = 1;

			f( d + 1 );

			xx[i] = 0;
			ds[d + i] = 0;
			dd[ d- i + add ] = 0;
		}
	}

}


int main()
{
	fcin >> N;
	f( 0 );
	fcout << res << "\n";
}