J - ヌクレオチド Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 500

問題文

高橋君は世界征服のために 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