Coco runs a chocolate factory. The factory's machine produces chocolate in $3 \times N$ rectangular blocks. Coco intends to sell these blocks by dividing them into $\lfloor \frac{3N}{2} \rfloor$ pieces of size $1 \times 2$ or $2 \times 1$. Since $N$ is always odd, Coco decides to pick one $1 \times 1$ piece to eat and sell the remaining part. Given the value of $N$ and the position of the piece Coco ate (row $R$, column $C$), calculate the number of ways to divide the remaining chocolate block.

Input

The first line contains the number of test cases $T$. For each test case, the values of $N$, $R$, and $C$ are given on a single line.

Output

Print the answer for each test case on a new line. Since the answer can be very large, output the result modulo $10^9+7$.

Examples

Input 1

3
5 1 1
5 2 2
5 1 2

Output 1

15
8
0

Note

$1 \le T \le 100000$, $1 \le N \le 100000$, $1 \le R \le 3$, $1 \le C \le N$, $N$ is odd.