問題文

$A$ 個の ( 、$B$ 個の ) 、$C$ 個の o 、$D$ 個の x からなる長さ $A+B+C+D$ の文字列のうち、次の条件を満たすものの個数を $10^9+7$ で割った余りを求めてください。

• 登場するすべての o を () に、x を )( に置き換えて得られる文字列は括弧の対応が取れている文字列である。

$T$ 個のテストケースについて答えてください。

制約

• $1\le T\le 10^5$
• $0\le A,B,C,D\le 10^5$
• $A+B+C+D\ge 1$
• 入力はすべて整数

入力

$T$
$\text{case}_1$
$\text{case}_2$
$\vdots$
$\text{case}_T$

各テストケースは以下の形式で与えられます。

$A$ $B$ $C$ $D$

出力

$T$ 行出力してください。$i$ 行目には、$i$ 番目のテストケースに対する答えを出力してください。

サンプル

3
1 1 1 1
31 41 59 26
999 999 0 1234

4
0
479533106