modified-paths-counting-in-a-rectangle 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 xth Rectangle is (Nx * Mx),where 1<=x<=K.
  From each rectangle x, Alice cuts a rect. of dimension (Px*Qx), where 1<=x<=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<=10
2<=(Nx,Mx)<=5*10^5
1<=Px<Nx
1<=Qx<Mx

The Time Limit is just 1 second.
Example:
K=1

N1=2 M1=2

P1=1 Q1=1

Answer: 5 ways
I 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.
 A: Let's restrict the study only to one of the K rectangles. Let's assume that N and M are respectively its height and width, and that P and Q are the height and width of the rectangle that gets cut off it. Let's refer to a coordinate system with origin on the top-left corner of the rectangle and x and y axis oriented right and down respectively.
The number of possible paths from the top-left corner to the bottom-right corner is given by:
$$
\frac{(N+M)!}{N!M!}
$$
From the number above we must subtract the number of paths not passing by the removed rectangle. This is all the paths not having a point on the vertical segment (M-Q+1, 0) - (M-Q+1, P-1).
The number of paths passing by a specific point (x, y) is given by:
$$
\frac{(x+y)!}{x!y!}\frac{[(M+N)-(x+y)]!}{(M-x)!(N-y)!}
$$
Hence the number we are looking for is:
$$
\frac{(N+M)!}{N!M!}-\sum_{y=0}^{P-1}{\frac{(M-Q+1+y)!}{(M-Q+1)!y!}\frac{(N+Q-1-y)!}{(Q-1)!(N-y)!}}
$$
I wouldn't know how to put that sum in closed form though.
A: (I'm going to scrap your $x$ subscript, and consider a single case given by $(N,M,P,Q)$. I use $x$ as my $x$-coordinate.)
Let $H$ be the horizontal line segment from $(0,M-Q)$ to $(N-P,M-Q)$ that extends the lower boundary of the cut-out rectangle across the uncut part. Consider a point $(x,y)$ on $H$. Let $U(x,y)$ be the number of paths from the top left corner $(0,M)$ to $(x,y)$ that first meet $H$ at $(x,y)$; and let $L(x,y)$ be the number of paths from $(x,y)$ to the bottom right corner $(N,0)$. Then the number of paths from $(0,M)$ to $(N,0)$ that first meet $H$ at $(x,y$) is just $U(x,y)L(x,y)$, and we get the total by summing this over $x$ from $0$ to $N-P$.
Now let $R(i,j)$ be the number of paths from one corner of an $i \times j$ rectangle to the opposite corner: $$R(i,j)=\frac{(i+j)!}{i!j!}$$(as you know). We get immediately $L(x,y)=R(N-x,M-Q)$. And for $U(x,y)$, note that a path that first meets $H$ at $(x,y)$ must pass through $(x,y+1)$, so $U(x,y)$ is just $R(x,Q-1)$.
A: We start from the common corner grid (B,N-A) of the rectangle and the cut part. Now, we start from grid (0,0) and find path till that corner multiplied by paths from that corner till grid (N+1,M+1) , i.e the first term of above expression. Now further we move one grid back and calculate path from grid (0,0) till that grid multiplied by paths from there to grid (N+1,M+1) but removing the cases where common grid is used. Similarly , following above process till grid (B,N-A-1) to (B,0) we get the result.
Thus,You may use the formula I have derived:
$${N-A+B \choose B} {M-B+A \choose A} + \sum_{r=0}^{N-A-1} {B+r \choose r}  {N-r+M-B-1 \choose N-r}$$
where $A=P$ and $B=Q$.
You need to simplify it further to convert into $O(n \log n)$ solution.
