問題文

りあんさんは文字列 "A" を AA 個、文字列 "B" を BB 個、文字列 "AB" を CC 個持っています。
これらを全て連結して長さ A+B+2CA + B + 2C の文字列を作るとき、作られる文字列としてありうるものが何通りあるかを求めてください。
ただし、この値は非常に大きくなる可能性があるので、109+710 ^ 9 + 7 で割ったあまりを出力してください。

この問題では一つの入力につきテストケースが TT 個与えられます。

制約

  • 入力は全て整数
  • 1T2,0001 \le T \le 2{,}000
  • 0A,B,C1,0000 \le A, B, C \le 1{,}000
  • 1A+B+C1 \le A + B + C

入力

入力は以下の形式で与えられます。

TT
A1A_1 B1B_1 C1C_1
:
ATA_T BTB_T CTC_T

出力

TT 行出力してください。
i (1iT)i \ (1 \le i \le T) 行目には ii ケース目 (Ai,Bi,Ci)(A_i, B_i, C_i) の答えを出力してください。

入出力例

入力例 1

5
1 1 1
1 3 1
10 0 10
1000 1000 0
1000 1000 1000

出力例 1

5
14
184756
72475738
314702404

Submit


Go (1.21)