Binomial Sum of Products

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