配点: 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 表示项目数。
制約
- 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