ピラミッド - 2D編

题意翻译

创造一个如图所示的数字金字塔。自上而下的第 $i$ 行,从左至右的第 $j$ 个点表示为 $(i,j)$。 ![](https://cdn.luogu.com.cn/upload/image_hosting/1iy508eb.png) 如需取点 $(i,j)$ ,则必须先取点 $(i-1,j-1)$ 和点 $(i-1,j)$ (图中视为取这一个点所直接连接的两个 $i-1$ 行的点)(超过边界则不需要取),每次最多取两个点。 输入操作总次数 $ T $ ,在 $ T $ 行内每一行输入4个值$ A,B,C,D$ ,要求输出取点 $(A,B)$ 与 $(C,D)$ 的最小方案数之和(方案数根据取点顺序的不同而不同)(结果对 $1e9+1$ 取余)。

题目描述

[problemUrl]: https://atcoder.jp/contests/gwcontest2015/tasks/gw2015_j 伊織ちゃんのマイブームはピラミッドである。 伊織ちゃんはピラミッドを題材にした問題を思いついた。しかし、その問題は既出の問題だということが発覚し、伊織ちゃんは拗ねてしまった。そして、伊織ちゃんは別の問題を考えることにした。 段数が無限である $ 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 $ つの取り方は違う取り方であるということにする。また、同じタイミングで $ 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

说明

### Sample Explanation 1 $ 1 $ 個目のテストケースでは以下の $ 2 $ 通りの取り方がある。 - 石 $ (1,1) $、石 $ (2,2) $、石 $ (2,1) $ の順に取る。 - 石 $ (1,1) $、石 $ (2,1) $、石 $ (2,2) $ の順に取る。