Zhu’s Math Problem

Problem 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$

Sample Input

1
2 1 1 1

Sample Output

10

Author

UESTC

Source

2016 Multi-University Training Contest 6