I am doing this question using the usual DP approach, i.e.
dp[i][j] = dp[i-1][j] + dp[i][j-1] + dp[i-1][j-1]
That approach gave TLE in both Python and Pypy. What exactly am i expected to do in this problem??
P.s. I also tried considering the problem as one in combinatorics,
i.e. considering a string of U and R, then finding out ways possible without any consideration to diagonal elements. Then considering diagonal elements as combinations of "UR" (Up and Right) and summing up all the terms :--
from math import factorial
def lvader(a, b) :
mod = 1000000007
s = 0
q = min(a, b)
p = factorial(a+b)
for i in xrange(q) :
s += p / (factorial(a-i) * factorial(b-i) * factorial(i))
return s
t = int(raw_input())
mod = 1000000007
for _ in xrange(t) :
x, y, a, b = map(int, raw_input().split())
print (lvader(a-x, b-y)) % mod