問題文

縦 $H$ マス 横 $W$ マスのグリッドがあります。上から $i$ 行目、左から $j$ 列目のマスを $(i,j)$ と表します。

Natsubi くんがこのグリッド上を $(1,1)$ から $(H,W)$ まで移動します。彼は $(i,j)$ にいるとき、$(i+1,j)$ または $(i,j+1)$ に動く事が出来ます。グリッドの外に移動することはできません。

ある移動経路について、そのジグザグ度を以下のように定義します。

• 経路上のマスのうち、そこで経路が曲がっているものの数

ここで、あるマス $(i,j)$ で「経路が曲がっている」とは、以下の条件のうちいずれかが成り立っていることを指します。

• $(i-1,j),(i,j),(i,j+1)$ がすべて存在し、かつ経路がそれらすべてを通っている。
• $(i,j-1),(i,j),(i+1,j)$ がすべて存在し、かつ経路がそれらすべてを通っている。

$H,W$ が与えられるので、${\displaystyle (\genfrac{}{}{0ex}{}{H+W-2}{H-1})}$ 個ある移動経路すべてについてジグザグ度を求め、その総和を答えてください。

ただし、答えは非常に大きくなることがあるので、${10}^9+7$ （素数）で割った余りを出力してください。

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

入力

入力は標準入力から与えられます。入力の $1$ 行目は以下の通りです。

$T$

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

$HW$

• 入力はすべて整数
• $1\le T\le {10}^5$
• $1\le H,W\le 2\times {10}^5$

出力

各テストケースに対し、答えを出力してください。テストケースごとに改行してください。

サンプル

サンプル1

入力サンプルをコピー

入力

4
2 3
1 10
1 1
200000 200000

出力

4
0
0
316943316

• $1$ つ目のケースについて：考えられる移動経路は下図の $3$ 通りです。ジグザグ度はそれぞれ $1,2,1$ なので、$4$ が答えです。
• $2$ つ目のケースについて：そもそも曲がりようがありません。
• $3$ つ目のケースについて：もはや移動すらしていませんが、これも答えは $0$ です。
• $4$ つ目のケースについて：求めた答えを ${10}^9+7$ で割った余りを出力するのを忘れないでください。