题目描述

Zhu 是一位强大的 ACMer / 守望先锋玩家。现在一条"咸鱼"来问 Zhu 一道难题，Zhu 觉得这道题太简单了，所以他想知道你能不能解决它。

给定四个整数 $A,B,C,D$，请问有多少个不同的四元组 $(a,b,c,d)$ 同时满足：

• $a+c > b+d$
• $a+d \geq b+c$
• $0\le a\le A$
• $0\le b\le B$
• $0\le c\le C$
• $0\le d\le D$

输入格式

第一行是一个正整数 $T(1\le T\le 1000)$，表示有 $T$ 组测试数据。

接下来 $T$ 行，每行四个整数 $A,B,C,D(0\le A,B,C,D \le 10^{18})$。

输出格式

对每组测试数据，输出答案对 $10^9+7$ 取模后的结果（答案可能很大）。

样例

输入：

1
2 1 1 1

输出：

10

数据范围与子任务

\begin{array}{|c|c|c|} \hline \textbf{子任务} & \textbf{分值} & \textbf{数据范围} \\ \hline 1 & 20 & A,B,C,D\le 20 \\ \hline 2 & 30 & A,B,C,D\le 1000 \\ \hline 3 & 50 & A,B,C,D\le 10^{18} \\ \hline \end{array}

• 对于 100% 的数据：$1\le T\le 1000,0\le A,B,C,D \le 10^{18}$。