Binomial Sum of Products
Tag(s):

## Dynamic Programming, Easy, Pascal's rule, Pascal's triangle, Two dimensional

Problem
Editorial
Analytics

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

• $1\leq q \leq 1000$
• $0 \leq a \leq b \leq 1000$
• $0 \leq c \leq d \leq 1000$
SAMPLE INPUT
3
0 0 0 1
4 5 1 2
4 5 5 6
SAMPLE OUTPUT
0
74
510

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

Time Limit: 1,0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

Think-A-Thon

OTHER PROBLEMS OF THIS CHALLENGE
• Algorithms > Dynamic Programming
• Algorithms > Dynamic Programming
• Data Structures > Advanced Data Structures
Уведомления

?