J - ヌクレオチド Editorial

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 500500

問題文

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

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

  • 各要素は 0,10, 1 のどちらか。
  • 回文である。つまり、 1iNx1 \leq i \leq N_x について、 Ai=ANx+1iA_i = A_{N_x+1-i} が満たされる。
  • 転倒数は KxK_x である。ただし、転倒数とは、整数組 (i,j)(i, j) であって、i<ji < j かつ Ai>AjA_i > A_j となるものの個数を表す。
条件を満たす数列 AiA_i は何通りあるでしょうか。答えは非常に大きな数になる可能性があるので、 109+710^9+7 で割った余りを求めてください。

制約

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

入力

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

Q Q 
N1 K1N_1\ K_1 
\vdots
NQ KQN_Q\ K_Q 

出力

QQ 行出力してください。

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


入力例 1Copy

Copy
4
3 0
3 1
3 2
3 3

出力例 1Copy

Copy
2
2
0
0

入力例 2Copy

Copy
5
4 2
5 3
6 4
16 8
869 120

出力例 2Copy

Copy
2
4
6
0
0


2024-12-19 (Thu)
01:29:10 +00:00