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 - a'| 时,骑士可以从方格 $$$(a, b)$$$ 移动到方格 $$$(a', b')$$$。 > 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$$$。
示例
输入 #1
2 3 4 5 6 5 5 8 8
输出 #1
27 70