AT_iroha2019_day1_j ヌクレオチド

[problemUrl]: https://atcoder.jp/contests/iroha2019-day1/tasks/iroha2019_day1_j 高橋君は世界征服のために $ 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\ \ A_j $ となるものの個数を表す。 条件を満たす数列 $ A_i $ は何通りあるでしょうか。答えは非常に大きな数になる可能性があるので、 $ 10^9+7 $ で割った余りを求めてください。

入力は以下の形式で標準入力から与えられます。 > $ Q $ $ N_1\ K_1 $ $ \vdots $ $ N_Q\ K_Q $

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

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