All Tracks Algorithms Dynamic Programming 2 Dimensional Problem

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...
Your Rating:

Contributor

This Problem was Asked in

Hewlett Packard

Challenge Name

Think-A-Thon

OTHER PROBLEMS OF THIS CHALLENGE
Уведомления
View All Notifications

?