I was solving the following problem. But I am not able to think of an efficient algorithm for this modified version of problem. The problem statement is:We are given K Rectangles. The dimensions of $x$-th Rectangle is ($N_x \times M_x$), where $1\leq x \leq K$.  From each rectangle $x$ , Alice Cuts  a rect. of dimension ($P_x \times Q_x$), where $1 \leq x \leq K$ ,  from the Top-Right Corner and trashes the cut portion.Initially Alice placed a robot, at the top left corner of each rectangle. He is very interested to find the number of ways, each robot can reach the bottom-right corner (target) using the following rules:The robot can only move 1 unit right* or the robot can only move 1 unit downward.The robot cannot move upward, can't move even left and can't move even diagonally.The robot can move on rectangle boundary.The number of ways can be very large. Thus, Answer = (Number of ways) mod 10^9+7.Constraints is very large:1<=K<=102<=(Nx,Mx)<=5*10^51<=Px<Nx1<=Qx<MxThe Time Limit is just 1 second.Example:K=1N1=2 M1=2P1=1 Q1=1Answer: 5 waysI had solved the easier version of this problem (Using Pascal triangle + Combinatorics), when no portion of rectangle is cut/removed. But I don't know how to solve the above modified problem, where a small rectangle is cut from top-right Corner of the original rectangle.
Modified paths Counting in a Rectangle
algorithms;combinatorics;dynamic programming