#include <iostream>
#include <cstdio>
#include <cstdlib>

using namespace std;

long** validPathCount;
int pathCount;
int maxDown;
int maxRight;

long intpow(int base, int power)
{
	if (power==0) 
		return 1;

	return base * intpow(base, power-1);

}

long convertedCoordinate(long* inCoord, bool DownRight)
{
	int a;
	int result = 0;

	for (a=0;a<pathCount;a++)
	{
		if (DownRight) 
			result = result + intpow(maxDown, a) * inCoord[a];
		else
			result = result + intpow(maxRight, a) * inCoord[a];
	}

	return result;
}

long getPathCount(long* xCoord, long* yCoord)
{
	int result;
	int longest;
	int a;
	int lastx;
	int lxc;
	int lyc;

	// NEVER let the algorithm see invalid choices.
	for (a=0;a<pathCount;a++)
		if ((xCoord[a] == -1)||(yCoord[a]==-1))
			return 0;

	// Have I done this before?
	if (validPathCount[convertedCoordinate(yCoord, false)][convertedCoordinate(xCoord, true)] == -1)
	{
		//Take care of basis cases.

		//The ultimate basis case
		if ((convertedCoordinate(xCoord, true) == 0) && (convertedCoordinate(yCoord, false) == 0))
		{
			result = 1;
		}
		else
		{
			//Basis case where all paths of the longest length are not properly ordered
			//First, determine the longest length.

			longest = 0;
			for (a=0;a<pathCount;a++)
				if (xCoord[a] + yCoord[a] > longest)
					longest = xCoord[a] + yCoord[a];

			//Now be certain that all paths of this length are at least properly oriented.  

			lastx = 0;
			result = -1;
			for (a=0;a<pathCount;a++)
				if (xCoord[a] + yCoord[a] == longest)
				{
				 if (xCoord[a] < lastx)
				 {
					 result = 0;
					 break;
				 }

				 lastx = xCoord[a];
				}

			//Otherwise, actually calculate this beast.
			//Use the algorithm to "shorten" each path of the longest length.
			//I have flagged result = -1 if I still haven't figured it out.
			if (result == -1)
			{	
			 result = 0;

			 //I think I only need to consider *any* longest staircase.  The recursion will take care of the rest.
			 //I know this is theoretically bad style--but it's FAST style.
			for (a=0;a<pathCount;a++)
				if (xCoord[a] + yCoord[a] == longest)
				{
				 lxc = xCoord[a];
				 lyc = yCoord[a];

				 xCoord[a] = xCoord[a] - 1;
				 
				 result = getPathCount(xCoord, yCoord);

				 xCoord[a] = lxc;
				 yCoord[a] = yCoord[a] - 1;

				 result += getPathCount(xCoord, yCoord);

				 yCoord[a] = lyc;
				}
			}
		}

		//Memoize now
		validPathCount[convertedCoordinate(yCoord, false)][convertedCoordinate(xCoord, true)] = result;
	}
		
	return validPathCount[convertedCoordinate(yCoord, false)][convertedCoordinate(xCoord, true)];
}

void main() {

	long a;
	long b;
	long tx;
	long ty;
	long result;
	long cache_IPMDPC;
	long cache_IPMRPC;
	long quit;
	long* xCoords;
	long* yCoords;

	//Get local parameters

	printf("Number of paths? ");
	scanf("%d", &pathCount);

	printf("Height? ");
	scanf("%d", &maxDown);

	printf("Width? ");
	scanf("%d", &maxRight);

	//printf("Keep within distance of leftmost (-1 to not specify)? ");
	//printf("Max down (-1 to not specify)? ");
	//printf("Max right? (-1 to not specify)? ");
	//printf("Max looparound (Y/N)? ");

	//Report variables (for text output)

	printf("\n\n");
	printf("Variable Report:\n");
	printf("Path Count: %d\n", pathCount);
	printf("Height    : %d\n", maxDown);
	printf("Width     : %d\n", maxRight);
	printf("\n");

	//Allocate memory.  I'm going to use a base-system to interleave the paths.

	//These cache variables will reduce the number of times I must call this function.
	cache_IPMDPC = intpow(maxDown, pathCount);
	cache_IPMRPC = intpow(maxRight, pathCount);

	validPathCount = new long*[cache_IPMDPC];
	for (a=0;a<cache_IPMDPC;a++)
	{
		validPathCount[a] = new long[cache_IPMRPC];
		for (b=0;b<cache_IPMRPC;b++)
			validPathCount[a][b] = -1;
	}

	xCoords = new long[pathCount];
	yCoords = new long[pathCount];

	//Actually call the function for some desired points.
	
	do {

		for (a=0;a<pathCount;a++)
		{
			printf("Enter Coordinate for LOWEST path (X Y): ");
			scanf("%d %d", &tx, &ty);
			xCoords[a] = tx;
			yCoords[a] = ty;
		}

		result = getPathCount(xCoords, yCoords);

		printf("Result: %d\n", result);

		printf("Continue (0 for no)? ");
		scanf("%d", &quit);

	} while (quit!=0);

	//Deallocate memory

	for (a=0;a<cache_IPMDPC;a++)
		delete [] validPathCount[a];

	delete [] validPathCount;
	delete [] xCoords;
	delete [] yCoords;

	printf("\n\nDone.\n");
}