Problem Description

Takahashi has decided to create $ Q $ viruses for world domination. To do this, it is important to consider the nucleotide sequence, but there are too many candidates, so he has come to you for help.

The nucleotide sequence of the $ x $-th virus he wants to create can be represented as a sequence of length $ N_x $, $A_1,\ A_2,\ \cdots,\ A_{N_x}$, that satisfies the following conditions:

• Each element is either $ 0 $ or $ 1 $.
• It is a palindrome. That is, for $1\ \leq\ i\ \leq\ N_x$, $A_i\ =\ A_{N_x+1-i}$ is satisfied.
• The inversion number is $ K_x $. The inversion number is the number of integer pairs $(i,\ j)$ such that $i\ <\ j$ and $A_i\ >\ A_j$.

How many such sequences $ A_i $ are possible? The answer could be a very large number, so please find the remainder when divided by $ 10^9+7 $.

Input Format

The input is given from the standard input in the following format:

$ Q $ $N_1\ K_1$ $\vdots$ $N_Q\ K_Q$

Output Format

Output $ Q $ lines.

The $ i $-th line should contain the number of possible sequences for the $ i $-th virus's nucleotide sequence, modulo $ 10^9+7 $.

Sample Input and Output

Sample Input #1

4
3 0
3 1
3 2
3 3

Sample Output #1

2
2
0
0

Sample Input #2

5
4 2
5 3
6 4
16 8
869 120

Sample Output #2

2
4
6
0
0

Notes/Hints

Constraints

• $1\ \leq\ Q\ \leq\ 10^5$
• $1\ \leq\ N_i\ \leq\ 10^5$
• $0\ \leq\ K_i\ \leq\ N_i(N_i\ -\ 1)\ /\ 2$
• All inputs are integers

见题面 Input 部分

见题面 Output 部分