주 선생님과 수학 문제

주 선생님은 한때 다음과 같은 수학 문제를 떠올렸다.

네 정수 $A$, $B$, $C$, $D$가 주어질 때, 다음 조건을 모두 만족하는 정수 네 쌍 $(a, b, c, d)$는 몇 개인가?

$\begin{array}{c} 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 \\ \end{array}$

그러한 네 쌍의 개수를 구하라. 답이 매우 클 수 있으므로 $10^{9} + 7$로 나눈 나머지를 계산하면 충분하다.

첫째 줄에 테스트 케이스의 수 $T$가 주어진다 ($1 \le T \le 1000$).

각 테스트 케이스는 한 줄에 네 정수 $A$, $B$, $C$, $D$로 주어진다 ($0 \le A, B, C, D \le 10^{18}$).

각 테스트 케이스마다 $10^{9} + 7$로 나눈 답을 한 줄에 하나씩 출력한다.