AT_gw2015_j ピラミッド - 2D編

[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\

入力は以下の形式で標準入力から与えられる。 > $ 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 $ で割った余りを出力せよ。出力の末尾にも改行を入れること。

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