CF1425C Captain of Knights

Chanek 先生刚刚赢得了全国国际象棋锦标赛，并获得了一块巨大的 $N \times M$ 棋盘。玩腻了传统的国际象棋后，Chanek 先生现在定义了一个函数 $F(X, Y)$，表示骑士从 $(1, 1)$ 走到 $(X, Y)$ 所需的最少步数。发现求 $F(X, Y)$ 太简单了，于是 Chanek 先生又定义了： $$ G(X, Y) = \sum_{i=X}^{N} \sum_{j=Y}^{M} F(i, j) $$ 给定 $X$ 和 $Y$，请你求出 $G(X, Y)$ 的值。 骑士可以从 $(a, b)$ 走到 $(a', b')$，当且仅当 $|a - a'| > 0$，$|b - b'| > 0$，且 $|a - a'| + |b - b'| = 3$。当然，骑士不能离开棋盘。

第一行包含一个整数 $T$ $(1 \le T \le 100)$，表示测试用例的数量。 每个测试用例包含一行，包含四个整数 $X$、$Y$、$N$、$M$ $(3 \leq X \leq N \leq 10^9, 3 \leq Y \leq M \leq 10^9)$。

对于每个测试用例，输出一行 $G(X, Y)$ 对 $10^9 + 7$ 取模的结果。

由 ChatGPT 4.1 翻译