问题描述

高桥君为了征服世界决定制造 $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

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