J - ピラミッド - 2D編 解説 /

実行時間制限: 2 sec / メモリ制限: 256 MB

問題文

伊織ちゃんのマイブームはピラミッドである。

伊織ちゃんはピラミッドを題材にした問題を思いついた。しかし、その問題は既出の問題だということが発覚し、伊織ちゃんは拗ねてしまった。そして、伊織ちゃんは別の問題を考えることにした。

段数が無限である 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

1 個目のテストケースでは以下の 2 通りの取り方がある。

  • 石 (1,1)、石 (2,2)、石 (2,1) の順に取る。
  • 石 (1,1)、石 (2,1)、石 (2,2) の順に取る。