AT_gw2015_j.ピラミッド - 2D編

伊织酱最近迷上了金字塔。

伊织酱想出了一个以金字塔为主题的问题。然而，她发现这个问题已经有人出过了，于是她闷闷不乐。于是，伊织酱决定再想一个新的问题。

现在考虑一个层数无限的二维金字塔。从上往下第 $i\ (1 \leq i)$ 层，从左往右第 $j\ (1 \leq j \leq i)$ 个石头，记作石头 $(i, j)$。现在考虑取走石头 $(A, B)$ 和石头 $(C, D)$。要取走石头 $(i, j)$，必须先取走石头 $(i-1, j-1)$ 和石头 $(i-1, j)$（当 $i-1 < 1$ 或 $j-1 < 1$ 或 $j > i$ 时，这些石头本来就不存在，无需取走）。请问，有多少种取石头的方法，使得取走的石头总数最少？注意，取石头的顺序不同视为不同的方法，且每次只能取一个石头，不能同时取多个。

输入为以下格式，从标准输入读取。

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

• 第 $1$ 行为整数 $T\ (1 \leq T \leq 300000)$，表示测试用例的个数。
• 接下来 $T$ 行，每行包含 $4$ 个整数 $A_i\ (1 \leq A_i \leq 10^6)$，$B_i\ (1 \leq B_i \leq A_i)$，$C_i\ (1 \leq C_i \leq 10^6)$，$D_i\ (1 \leq D_i \leq C_i)$，表示第 $i$ 个测试用例的 $A,B,C,D$。保证 $A_i \neq C_i$ 或 $B_i \neq D_i$，且需要取的石头总数不超过 $10^6$。

输出共 $T$ 行，第 $i\ (1 \leq i \leq T)$ 行输出第 $i$ 个测试用例的答案，对 $10^9+7$ 取模。输出末尾需换行。

样例解释 1

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

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

由 ChatGPT 4.1 翻译