有一个石子金字塔。该金字塔由 $10^6$ 层组成，第 $i$ 层（$1 \le i \le 10^6$）包含 $i$ 个石子。第 $i$ 层中的第 $j$ 个石子被标记为 $(i, j)$。

为了取走金字塔中的石子 $(i, j)$，必须先取走 $(i - 1, j - 1)$ 和 $(i - 1, j)$（如果这些石子存在的话）。

你想要取走两个石子 $(A, B)$ 和 $(C, D)$。你希望通过取走最少数量的石子来完成此操作。对于每个 $i$，有多少种不同的取法？如果对于某个 $i$，你从金字塔中取走的第 $i$ 个石子不同，则认为这两种取法是不同的。

给定 $T$ 组询问。第 $i$ 组询问的参数由 $(A_i, B_i, C_i, D_i)$ 给出。对于每组询问，计算答案对 $10^9 + 7$ 取模的结果。

输入格式

第一行包含一个整数 $T$。 接下来的 $T$ 行，每行包含四个整数 $A_i, B_i, C_i, D_i$。

数据范围

• $1 \le T \le 300000$
• $1 \le B_i \le A_i \le 10^6$
• $1 \le D_i \le C_i \le 10^6$
• 保证可以通过取走最多 $10^6$ 个石子来同时取走 $(A_i, B_i)$ 和 $(C_i, D_i)$。
• 对于每个 $i$，$(A_i, B_i)$ 和 $(C_i, D_i)$ 是不同的。

输出格式

输出 $T$ 行。第 $i$ 行输出第 $i$ 组询问的答案。

样例

输入 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, 1), (2, 2), (2, 1)$。
• 按顺序取走石子 $(1, 1), (2, 1), (2, 2)$。