Problem Statement :You are situated in an N dimensional grid at position (x1,x2,...,xN). The dimensions of the grid are (D1,D2,...DN). In one step, you can walk one step ahead or behind in any one of the N dimensions. (So there are always 2N possible different moves). In how many ways can you take M steps such that you do not leave the grid at any point? You leave the grid if at any point xi, either xi0 or xi>Di.Input Format The first line contains the number of test cases T. T test cases follow. For each test case, the first line contains N and M, the second line contains x1,x2,,xN and the 3rd line contains D1,D2,,DN.Output Format Output T lines, one corresponding to each test case. Since the answer can be really huge, output it modulo 1000000007.Constraints1T101N101M3001Di1001xiDiSample Input12 31 12 3Sample Output12If this was in 1D the solution can be like this : solve(i+1)+solve(i-1);in 2D : solve(i+1,j)+solve(i-1,j)+solve(i,j+1)+solve(i,j-1);How can i program it for N Dimensions?Is their some general steps for making recursion statements like above which could help in making recursive statements Most solutions which i saw are in bottom up or top down manner i am not able to understand them ? is their any way to understand them ,as i have always practiced dp using recursion + memoization  i find it hard to understand them
How to apply recursion in this problem
dynamic programming;recursion