問題文

整数 $N$, $A$, $B$ が与えられます。

辺の長さが $N$ の白い正方形を座標平面の $(0,0), (N,0), (0,N), (N,N)$ に $4$ 頂点が重なるように置きます。

次に、この白い正方形の内部または周上に収まるように、辺の長さが $A$ の青い正方形と辺の長さが $B$ の赤い正方形を $1$ つずつ置きます。

ただし、正方形のどの辺も $x$ 軸または $y$ 軸と平行に置かれている必要があります。

また、青い正方形と赤い正方形の各頂点は格子点上に置かれている必要があります。

赤い正方形の内部と青い正方形の内部が重ならないように置く方法の数を $1,000,000,007$ で割ったあまりを求めてください。

$1$ つの入力につき、$T$ 個のテストケースに答えてください。

制約

• $1 \\leq T \\leq 10^5$
• $1 \\leq N \\leq 10^9$
• $1 \\leq A \\leq N$
• $1 \\leq B \\leq N$
• 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。入力の $1$ 行目は以下のとおりである。

$T$

そして、 $T$ 個のテストケースが続く。これらはそれぞれ以下の形式で与えられる。

$N$ $A$ $B$

出力

各テストケースについて、赤い正方形と青い正方形の内部が重ならないように置く方法の数を $1,000,000,007$ で割ったあまりを出力せよ。 各テストケースごとに改行せよ。

入力例 1

3
3 1 2
4 2 2
331895368 154715807 13941326

出力例 1

20
32
409369707

例えば最初のテストケースでは、重なりを気にせず青い正方形を置く方法が $9$ 通り、赤い正方形を置く方法が $4$ 通りあります。

赤い正方形をどこに置いても、赤い正方形の内部に重なるような青い正方形の置き方は $4$ 通りずつあります。

よって、赤い正方形の内部と青い正方形の内部が重ならないように置く方法の数は、 $9 \\times 4 - 4 \\times 4 = 20$ 通りです。

赤い正方形と青い正方形が周上のみを共有するとき、例えば青い正方形の左下の頂点が $(0,0)$、赤い正方形の左下の頂点が $(0,1)$ のときは赤い正方形と青い正方形の内部が重なっていないことに注意してください。