#include <fstream>
using namespace std;
ifstream in("damesah.in");
ofstream out("damesah.out");
 
const int nmax = 18;
int n, pr[nmax], rasp;
bool ln[nmax], cl[nmax * nmax], dg[nmax * nmax];
 
void back(int lvl)
{
    if(lvl>n)
	{
        if(rasp==0) 
		{
			for(int j = 1; j<=n; j++)
				out<<pr[j]<<' ';
			out<<'\n';
		}
		
		rasp++;
	}

    for(pr[lvl] = 1; pr[lvl]<=n; pr[lvl]++)
	{
		if(ln[pr[lvl]]==0 && cl[lvl - pr[lvl] + n]==0 && dg[lvl + pr[lvl]]==0)
		{
			ln[pr[lvl]] = cl[lvl - pr[lvl] + n] = dg[lvl + pr[lvl]] = 1;

			back(lvl + 1);
			ln[pr[lvl]] = cl[lvl - pr[lvl] + n] = dg[lvl + pr[lvl]] = 0;
		}
	}
}
 
int main()
{
	int player_unu=0;

    in>>n;

    back(1);

    out<<rasp<<'\n';

	return player_unu;
}