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

using namespace std;

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

long cache_IPMDPC;
long cache_IPMRPC;
long cache_IMSTRK;

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

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

}

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

	for (a=0;a<pathCount;a++)
		result = result + intpow(base, a) * inCoord[a];

	return result;
}

bool iterate(long* var, long size, long max)
{
	int a;

	for (a=0;a<size;a++)
	{
		var[a] = var[a] + 1;

		if (var[a] == max)
		{
			var[a] = 0;
		}
		else
			return true;
	}

	return false;

}

long getPathCount(long* xCoord, long* yCoord, bool total = true, long* selectedstreaks = 0)
{
	int result;
	int longest;
	int a;
	int lastx;
	int lxc;
	int lyc;
	int streak;
	long* streaks;

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

	if (total==false)
		for (a=0;a<pathCount;a++)
			if (selectedstreaks[a]<0)
				return 0;


	//If I am totalling this, what I really want is the sum at this point for every choice of selectedstreaks.
	if (total) 
	{
		streaks = new long[pathCount];

		//Any that satisfies the maximum maxDStreak must automatically maxRStreak for the same problem.  The 
		//way the recursion works guarantees that.

		for (a=0;a<pathCount;a++)
			streaks[a] = maxDown;

		result = 0;

		//Now I actually have to count every possibility.  By definition of my arrays, this is it. 
		
		result = getPathCount(xCoord, yCoord,  false, streaks);

		delete [] streaks;
		return result;
	}

	// Have I done this before?
	if (validPathCount[convertedCoordinate(yCoord, maxRight)][convertedCoordinate(xCoord, maxDown)][convertedCoordinate(selectedstreaks, 2 + maxDStreak + maxRStreak)] == -1)
	{
		//Take care of basis cases.

		//The ultimate basis case
		if ((convertedCoordinate(xCoord, maxDown) == 0) && (convertedCoordinate(yCoord, maxRight) == 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.


			//This next little section should be the last modification to make the streaks work:

			//Use the existing algorithm for infinite.

			//For streaks, just use the logic that for a number>0, I mean that one less must exist in that direction.
			//For a number=0, it must have come from the other direction with *any* length.

			//START HERE------------------------------------------------------

			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)
				{

				 //MEANINGS:  ZERO in this selectedStreak means "All paths to this point are OK"
				 //           0-MaxDStreak:  "All paths with a streak of THIS SIZE or less going right are OK"
				 //           1+MaxDStreak-end:  "All paths with a streak of THIS SIZE or less going down are OK"

				 lxc = xCoord[a];
				 lyc = yCoord[a];

				 //The case where I don't care how far left the the path came to get here.
				 //e.g., any path incident from the right is OK with me.  I take 0 to mean in ANY case "I want valid sides of any length."
				
				xCoord[a] = xCoord[a] - 1;
		
				//Find valid paths for the one to the left shorter than the desired length.
				if (selectedstreaks[a] > maxDStreak) 
				{
					selectedstreaks[a] = selectedstreaks[a] - 1;
					result = getPathCount(xCoord, yCoord, false, selectedstreaks);
					selectedstreaks[a] = selectedstreaks[a] + 1;
				}
				else
				{  //If the desired length is unspecified in this dimension then find valid ones from the left
					if (maxRStreak>0)
					{
						streak = selectedstreaks[a];
						selectedstreaks[a] = 1 + maxDStreak + maxRStreak - 1;
						result += getPathCount(xCoord, yCoord, false, selectedstreaks);
						selectedstreaks[a] = streak;
					}
				}

				xCoord[a] = lxc;

				yCoord[a] = yCoord[a] - 1;
		
				//Find valid paths for the one to the left shorter than the desired length.
				if (selectedstreaks[a] <= maxDStreak) 
				{
					selectedstreaks[a] = selectedstreaks[a] - 1;
					result += getPathCount(xCoord, yCoord, false, selectedstreaks);
					selectedstreaks[a] = selectedstreaks[a] + 1;
				}
				else
				{  //If the desired length is unspecified in this dimension then find valid ones from the top
					if (maxDStreak>0)
					{
						streak = selectedstreaks[a];
						selectedstreaks[a] = maxDStreak-1;
						result += getPathCount(xCoord, yCoord, false, selectedstreaks);
						selectedstreaks[a] = streak;
					}
				}


				yCoord[a] = lyc;


				 break;
				}
			}
		}

		//Memoize now
		validPathCount[convertedCoordinate(yCoord, maxRight)][convertedCoordinate(xCoord, maxDown)][convertedCoordinate(selectedstreaks, 2 + maxDStreak + maxRStreak)] = result;
	}
		
	return validPathCount[convertedCoordinate(yCoord, maxRight)][convertedCoordinate(xCoord, maxDown)][convertedCoordinate(selectedstreaks, 2 + maxDStreak + maxRStreak)];
}

void main() {

	long a;
	long b;
	long c;
	long tx;
	long ty;
	long result;
	long cache_IPMDPC;
	long cache_IPMRPC;
	long cache_IMSTRK;
	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 streak?");
	scanf("%d", &maxDStreak);

	printf("Max right streak?");
	scanf("%d", &maxRStreak);

	//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("Down streak : %d\n", maxDStreak);
	printf("Right streak: %d\n", maxRStreak);
	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 these powers.
	cache_IPMDPC = intpow(maxDown, pathCount);
	cache_IPMRPC = intpow(maxRight, pathCount);
	cache_IMSTRK = intpow(2 + maxDStreak + maxRStreak, 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] = new long[cache_IMSTRK];
			for (c=0;c<cache_IMSTRK;c++)
			{
				validPathCount[a][b][c] = -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 remaining 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++)
	{
		for (b=0;b<cache_IPMRPC;b++)
			delete [] validPathCount[a][b];
		delete [] validPathCount[a];
	}
	delete [] validPathCount;

	delete [] xCoords;
	delete [] yCoords;

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