問題文

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

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

段数が無限である $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)$ の順に取る。