Migrated from Lutece 1447 Zhu’s Math Problem

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Zhu is a powerful ACMer/OverWatcher, now a salt-fish comes to ask Zhu a difficult problem. Zhu thinks that problem is so easy, so he wants to know whether you can solve it?

The problem content are as follows.

You are given four integers A , B , C , D , there are many different (a,b,c,d) satisfy $a+c>b+d$ && $a+d\ge b+c$ && $0\le a\le A$ && $0\le b\le B$ && $0\le c\le C$ && $0\le d\le D$ ?

Input

First Line is an positive integer $T(T\le 1000)$ , represents there are T test cases.

Four each test：

The first line contain four integers A , B , C , D.

You can assume that $0\le A,B,C,D\le 10^{18}$

Output

For each test case, output an positive integer represents answer, because the answer may be large , so you are only need to output answer mod $10^9+7$

Samples

1
2 1 1 1

10

Resources

2016 Multi-University Training Contest 6