← 返回题目列表

AtCoder · iroha2019_day1_j

J. 核苷酸

中文机器翻译题面 查看原题

配点: 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