There's a 5×N rectangular corridor in the hall's dojo, one place is already taken by a magic hanjō (1×1 square). You have to put tatamis (1×2 rectangle) in order to cover exactly the rest of the corridor. Sometimes it's possible, sometimes not!

Input

The input begins with the number T of test cases in a single line. In each of the next T lines there are an integer N the H-length of the corridor, and I, J the coordinates of the magic hanjō. See sample input for details format.

Output

For each test case, print the number of possibility to do the job, modulo 1000000007.

Example

Input:
3
1 C 1
3 B 2
5 A 1

Output:
1
8
192

Constraints

1 <= T <= 40 000

1 <= N <= 20 000

A <= I <= E

1 <= J <= N

Uniform, independent, random input in the range. Input had been 'filtered' to let only possible configurations.

You may try too : Grid Tiling, or Blocks for kids

Edit(19/I/2015, after cluster switch) : now my old code ends in 0.23s using PY3.4.

Edit(11-2-2017, after compiler update) : now my old code ends in 0.10s using PY3.5. New TL.