#include <stdio.h>
#include <stdbool.h>

#define N	17								// N >= 3

bool Node[2 * N + 1][N + 1];

unsigned long long Polygons;

void step(unsigned n, int h, int v, int h_right, int h_left, int v_up)
{
	if (Node[h][v]) return;

	if (n == 4 * N) {							// one vertical step away from start a(-1, 2) or b( 1, 2)
		Polygons++;
		return;
	}

	Node[h][v] = true;

	if (n % 2) {								// n odd: horizontal step

		if (h_right)
			step(n + 1, h + 1, v, h_right - 1, h_left, v_up);

		if (h_left)
			if (v > 1)
				step(n + 1, h - 1, v, h_right, h_left - 1, v_up);

	} else {								// n even: vertical step

		if (v_up)
			step(n + 1, h, v + 1, h_right, h_left, v_up - 1);

		if (v)
			if (v > 1 || h > N)
				step(n + 1, h, v - 1, h_right, h_left, v_up);
	}

	Node[h][v] = false;
}

int main()									// first two steps are fixed (N >= 3)
{
	Node[N - 1][2] = true;							// step 1a: (-1, 2) -> ( 0, 2) h right
	Node[N + 1][2] = true;							// step 1b: ( 1, 2) -> ( 0, 2) h left
	Node[N + 0][2] = true;							// step 2:  ( 0, 2) -> ( 0, 1) v down

	step(3, N + 0, 1, N, N, N);						// step 3 starts at ( 0, 1)

	printf("n=%d: %llu polygons.\n", N, Polygons);
}