← 返回题目列表

AtCoder · gw2015_j

J. 金字塔 - 2D 版

中文机器翻译题面 查看原题

問題文

伊织酱最近流行对金字塔感兴趣。

伊织酱想出了一个以金字塔为题材的问题。然而,发现这个问题是已有的问题,伊织酱因此生气了。于是,伊织酱决定考虑另一个问题。

考虑段数无限的 2 维金字塔。从上面开始 i (1 ≦ i) 第 n 段的左边第 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 就算作不同的取法。同时,在同一个时间点 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) 。 来自行
  • 2 来自行 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) 。