#include <cstdio>
#include <cmath>
using namespace std;

FILE *in = fopen ( "damesah.in" , "r" ) , *out = fopen ( "damesah.out" , "w" );

int i , n , solution [ 150 ] , countSolutions , line [ 150 ] , diag [ 150 ] , diagS [ 150 ];
bool notGood;

void printSolution()
{
	for ( i = 1 ; i <= n ; i ++ )
		fprintf ( out , "%d " , solution [ i ] );
}

void getNextValue ( int index )
{
	notGood = true;
	if ( solution [ index ] )
    {
        line [ solution [ index ] ] --;
        diag [ solution [ index ] - index + n ] --;
        diagS [ solution [ index] + index ] --;
    }
	while ( notGood )
	{
		solution [ index ] ++;
		notGood = false;
		//it's on the table
		if ( solution [ index ] > n ) { solution [ index ] = 0 ; return; }

		//it's not attacking on it's line or diagonal
        if ( line [ solution [ index ] ] || diag [ solution [ index ] - index + n ] || diagS [ solution [ index] + index ] )
            notGood = true;
	}
}

void placeQueens ( int index )
{
	while ( index > 0 )
	{
		if ( index == n + 1 ) // we have a solution
		{
			countSolutions ++;
			if ( countSolutions == 1 )
				printSolution();
            index --;
		}
		else
		{
			getNextValue ( index );
			if ( solution [ index ] == 0 )
				index --;
			else
            {
                line [ solution [ index ] ] ++;
                diag [ solution [ index ] - index + n ] ++;
                diagS [ solution [ index] + index ] ++;
				index ++;
            }
		}
	}
}

int main()
{
	//read
	fscanf ( in , "%d" , &n );
	placeQueens ( 1 );
	//print the number of solutions
	fprintf ( out , "\n%d\n" , countSolutions );
	return 0;
}