問題文
伊织酱最近流行对金字塔感兴趣。
伊织酱想出了一个以金字塔为题材的问题。然而,发现这个问题是已有的问题,伊织酱因此生气了。于是,伊织酱决定考虑另一个问题。
考虑段数无限的 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) 。