Binomial Sum of Products

★★★★★

3.2

15 votes

Dynamic Programming, Easy, Pascal's Rule, Pascal's rule, Two dimensional

Details

Problem

A function $f(x,y)$ is defined as

$f(x,y) = \binom{x}{y}$ if $x \geq y$ else x x y

where $\binom{x}{y} = \frac{x!}{y!(x-y)!}$

There will be total q queries and each query will have four integers i.e. a, b, c and d. You need to compute the value of

$\sum_{i = a}^b \prod_{j=c}^d$ $f(i,j)$ for every query.

As the output number can be very large. So, you need to print answer modulo $10^9+7$

Note: $0!=1$

Input Format

First line will have a single integer denoting the value of q.
Each line in next q lines will have four space separated integers denoting the value of a,b,c and d.

Output Format

Output q lines, where $i^{th}$ line denoting the answer represents the answer of the $i^{th}$ query modulo $10^9+7$ .

Constraints

Time Limit: 1

Memory Limit: 256

Source Limit:

Explanation

For Case 1, we need to find f(0,0) x f(0,1) = 1 x 0 = 0

For Case 2, we need to find f(4,1) x f(4,2) + f(5,1) x f(5,2) = 4 x 6 + 5 x 10 = 24 + 50 = 74

For Case 3, we need to find f(4,5) x f(4,6) + f(5,5) x f(5,6) = 20 x 24 + 1 x 30 = 480 + 30 = 510