import java.util.*;

public class CountPaths {
	private int[] myFieldRow, myFieldCol;
	private int myR, myC;

	public int inField(int r, int c) {
//		System.out.printf("(%d,%d) -> (%d,%d)\n", r, c, myR-r, c+1);
		for(int j = 0; j < myFieldRow.length; j++) {
			if(myFieldRow[j] == myR-r && myFieldCol[j] == c+1) {
				return j;
			}
		}
		return -1;
	}

	// Calculate the score for (r, c) by using the sum of (r-1, c) and (r, c-1).
	public int[][] neighborSum(int[][][][] grid, int r, int c) {
		int[] dr = {1, 0};
		int[] dc = {0, -1};
		int[][] score = new int[grid[0][0].length][grid[0][0].length];
		int specialField = inField(r, c);

		for(int i = 0; i < 2; i++) {
			int _r = r+dr[i];
			int _c = c+dc[i];
			if(_r >= 0 && _c >=0 && _r < grid.length &&_c < grid[_r].length) {
				for(int j = 0; j < (specialField >= 0 ? score.length-1 : score.length); j++) {
					if(specialField >= 0) {
						for(int k = 0; k <= specialField; k++)
							score[j+1][specialField] +=
								grid[_r][_c][j][k];
					} else {
						for(int k = 0; k < score.length; k++) {
							score[j][k] +=
								grid[_r][_c][j][k];
						}
					}
				}
			}
		}
/*		if(specialField >= 0) {
			System.out.printf("(%d,%d) field=%d:\n", r, c, specialField);
			for(int i = 0; i < score.length; i++) {
				for(int j = 0; j < score[i].length; j++) {
					System.out.print(score[i][j] + " ");
				}
				System.out.println("");
			}
		}
*/		return score;
	}

	boolean isEmpty(int[][][][] grid) {
		for(int r = 0; r < grid.length; r++) {
			for(int c = 0; c < grid[r].length; c++) {
				for(int n = 0; n < grid[r][c].length; n++) {
					for(int i = 0; i < grid[r][c][n].length; i++)
						if(grid[r][c][n][i] != 0)
							return false;
				}
			}
		}
		return true;
	}

	public void printGrid(int[][][][] grid, int n) {
		System.out.println("---");
		for(int r = 0; r < grid.length; r++) {
			for(int c = 0; c < grid[r].length; c++) {
				int sum = 0;
				for(int i = 0; i < grid[r][c][n].length; i++)
					sum += grid[r][c][n][i];
				System.out.printf("%2d ", sum);
			}
			System.out.println("");
		}
	}

	public int[] difPaths(int r, int c, int[] fieldrow, int[] fieldcol) {
		myFieldRow = fieldrow;
		myFieldCol = fieldcol;
		myR = r;
		myC = c;
		int n = fieldrow.length+1;

		// current[row][column][n-value][index corresponds to largest fieldrow encountered].
		int[][][][] current = new int[r][c][n][n], previous = null;
		current[r-1][0][0][0] = 1;

//		printGrid(current, 0);

		while(true) {
			previous = current;
			current = new int[r][c][n][n];
			for(int _r = 0; _r < r; _r++) {
				for(int _c = 0; _c < c; _c++) {
					current[_r][_c] = neighborSum(previous, _r, _c);
				}
			}
			if(isEmpty(current))
				break;
//			printGrid(current, 0);
		}

		int endPos = -1;
		// See if we missed the end case.
		for(int _n = 0; _n < n-1; _n++) {
			if(fieldrow[_n] == r && fieldcol[_n] == c) {
				endPos = _n;
				break;
			}
		}

		int[] nValues = new int[n];
		for(int _n = 0; _n < n; _n++) {
			for(int i = 0; i < n; i++) {
				if(endPos < 0 || i > endPos)
					nValues[_n] += previous[0][c-1][_n][i];
			}
		}
		return nValues;
	}

	public static void main(String[] args) {
		CountPaths countPaths = new CountPaths();
		int r = 50;
		int c = 50;
		int[] fieldrow = {50, 1};
		int[] fieldcol = {50, 1};
		System.out.println(Arrays.toString(countPaths.difPaths(r, c, fieldrow, fieldcol)));
	}
}