lol i dont remember how i did this question. this is wat i wrote as explanation, it explains the whole thing, i cant be bothered to read it to explain ur specific question

//A random walk in n dimensions can be split into random walk in each of the dimensions and analysed separately

//First, for each dimension i and 1 <= K <= m, oneDimension[i][K] calculates the number of random walks of length K //within the interval [1, D[i]]: //(1) For 1 <= point <= D[i], endPoint[i][K][point] stores the the number of length K random walks within [1, D[i]] that // ends at point //(2) endPoint[i][K+1][point] = endPoint[i][K][point-1] + endPoint[i][K][point+1] //(3) oneDimension[i][K] = sum of all the endPoint[i][K][point] for every 1 <= point <= D[i]

//For n dimensions, let multiDimension[n][K] be the number of random walks within the corresponding n-dimensional cube defined by //the D[i]'s //The dynamic programming part is: any such walk can be split into a walk A in dimension n, and a walk B in the remaining n-1 dimensions.

//Let binomial[n][k] be the binomial coefficient //Given a walk A of length l in dimension n, and a walk B of length K-l in the remaining n-1 dimensions, //they can be combined to become a walk H of length K in n dimensions. //There's binomial[K][l] many ways to insert the walk A into H, hence the number of length K walk in n dimensions that //can be decomposed into a length l walk in dimension n, and a length K-l walk in the remaining n-1 dimensions, is: // oneDimension[n][l] * multiDimension[n-1][K-l] * binomial[K][l] //=> multiDimension[n+1][K] = sum of all the oneDimension[n][l] * multiDimension[n-1][K-l] * binomial[K][l] for every 0 <= l <= K

//The time of this algorithm is O(300^2 + n * m^2)