class ResultEntry {
	public boolean done;
	public long value;

	public ResultEntry() {
		done = false;
	}
}

public class BinomialCoefMemoization implements IBinomialCoef {
	private ResultEntry[][] result;

	public long C(int n, int k) {
		result = new ResultEntry[n + 1][k + 1];

		for (int i = 0; i <= n; i++)
			for (int j = 0; j <= k; j++)
				result[i][j] = new ResultEntry();
		return C_with_memo(n, k);
	}

	private long C_with_memo(int n, int k) {
		if (result[n][k].done == true)
			return result[n][k].value;

		if ((k == 0) || (n == k)) {
			result[n][k].done = true;
			result[n][k].value = 1;
			return result[n][k].value;
		}

		result[n][k].done = true;
		result[n][k].value = C_with_memo(n - 1, k) + C_with_memo(n - 1, k - 1);
		return result[n][k].value;
	}
}