问题描述

伊织酱的兴趣是金字塔。

伊织酱想出了一个以金字塔为题材的问题。但是，后来发现这个问题已经被提出过了，所以伊织酱就有点不高兴了。然后，伊织酱决定思考另一个问题。

考虑一个层数无限的 $2$ 维金字塔。我们将从上到下的第 $i (1 ≦ i)$ 层左侧的第 $j (1 ≦ j ≦ i)$ 块石头称为石头 $(i,j)$。我们考虑取石头 $(A,B)$ 和石头 $(C,D)$。为了取石头 $(i,j)$，必须先取石头 $(i-1,j-1)$ 和石头 $(i-1,j)$（如果 $i-1 < 1$ 或者 $j-1 < 1$ 或者 $j > i$，那么石头不存在，不需要取）。在取石头 $(A,B)$ 和石头 $(C,D)$ 的方法中，有多少种取法使得取石头的数量最小？注意，取法根据取石头的顺序而区分，当取石头的顺序不同时，两种取法是不同的。此外，在同一时间内不能取 $2$ 个以上的石头。

输入

输入从标准输入中按以下格式给出。

$T$ $A_1$ $B_1$ $C_1$ $D_1$ $A_2$ $B_2$ $C_2$ $D_2$ : $A_T$ $B_T$ $C_T$ $D_T$

• 第 $1$ 行包含一个整数 $T (1 ≦ T ≦ 300,000)$，表示测试案例的数量。
• 接下来的 $T$ 行描述每个测试案例的信息。其中第 $i (1 ≦ i ≦ T)$ 行包含 $4$ 个整数 $A_i (1 ≦ A_i ≦ 10^6), B_i (1 ≦ B_i ≦ A_i), C_i (1 ≦ C_i ≦ 10^6), D_i (1 ≦ D_i ≦ C_i)$，表示第 $i$ 个测试案例中的 $A,B,C,D$ 的值。注意，保证 $A_i ≠ C_i$ 和 $B_i ≠ D_i$ 成立。此外，保证需要取的石头数量不超过 $10^6$。

输出

输出包含 $T$ 行。其中第 $i (1 ≦ i ≦ T)$ 行输出第 $i$ 个测试案例的答案除以 $10^9+7$ 的余数。输出末尾要有换行符。

示例输入1

6
2 1 2 2
1 1 1000000 1000000
3 2 5 3
5 2 4 3
2015 55 1700 1300
100 50 1000 500

示例输出1

2
1
42
252
926737422
143485143

第 $1$ 个测试案例有以下 $2$ 种取法：

• 按照顺序取石头 $(1,1)$、石头 $(2,2)$、石头 $(2,1)$。
• 按照顺序取石头 $(1,1)$、石头 $(2,1)$、石头 $(2,2)$。