問題文

高橋君は世界征服のために $Q$ 個のウイルスを作ることにしました。そのためには塩基列を考えることが重要ですが、あまりに候補が多すぎるのであなたに助けを求めてきました。

$x$ 番目に作りたいウイルスの塩基列は、長さ $N_x$ の数列 $A_1, A_2, \\cdots, A_{N_x}$ であって、以下の条件を満たすものとして表せます。

• 各要素は $0, 1$ のどちらか。
• 回文である。つまり、 $1 \\leq i \\leq N_x$ について、 $A_i = A_{N_x+1-i}$ が満たされる。
• 転倒数は $K_x$ である。ただし、転倒数とは、整数組 $(i, j)$ であって、$i < j$ かつ $A_i > A_j$ となるものの個数を表す。

条件を満たす数列 $A_i$ は何通りあるでしょうか。答えは非常に大きな数になる可能性があるので、 $10^9+7$ で割った余りを求めてください。

制約

• $1 \\leq Q \\leq 10^5$
• $1 \\leq N_i \\leq 10^5$
• $0 \\leq K_i \\leq N_i(N_i - 1) / 2$
• 入力はすべて整数

入力

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

$Q$ $N_1\\ K_1$ $\\vdots$ $N_Q\\ K_Q$

出力

$Q$ 行出力してください。

$i$ 行目には、$i$ 番目に作りたいウイルスの塩基列としてあり得る数列の個数を $10^9+7$ で割った余りを $1$ 行に出力してください。

入力例 1

4
3 0
3 1
3 2
3 3

出力例 1

2
2
0
0

入力例 2

5
4 2
5 3
6 4
16 8
869 120

出力例 2

2
4
6
0
0