// Include
#include <fstream>
using namespace std;

// Functii
void back(int line);
bool valide(int line, int column);

// Variabile
ifstream in("damesah.in");
ofstream out("damesah.out");

int num;
int stk[15];
int answer;
bool onColumn[15], onMainDiag[30], onSecondDiag[30];

// Main
int main()
{
	in >> num;
	
	back(1);
	
	out << '\n' << answer << '\n';
	
	in.close();
	out.close();
	return 0;
}

void back(int line)
{
	for(int column=1 ; column<=num ; ++column)
	{
		stk[line] = column;
		if(valide(line, column))
		{
			onColumn[column] = true;
			onMainDiag[line - column + num - 1] = true;
			onSecondDiag[line + column] = true;
			
			if(line == num)
			{
				if(++answer==1)
					for(int i=1 ; i<=num ; ++i)
						out << stk[i] << ' ';
			}
			else
				back(line+1);
			
			onColumn[column] = false;
			onMainDiag[line - column + num - 1] = false;
			onSecondDiag[line + column] = false;
		}
	}
}

bool valide(int line, int column)
{
	return 	!onColumn[column] &&
			!onMainDiag[line - column + num - 1] &&
			!onSecondDiag[line + column];
}