問題文


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

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

制約


  • 入力は全て整数

入力


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

T
A_1 B_1 C_1
:
A_T B_T C_T

出力


行出力してください。
行目には ケース目 の答えを出力してください。

入出力例


入力例 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.14)