DOJ2 - DOJO Corridor II

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

Corridor

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.


Added by:Francky
Date:2012-07-08
Time limit:0.400s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own problem

hide comments
2014-03-29 08:07:41 Francky
Same code from a multiaccount, -> one of them disqualified. Please do not use multi account. It 'steal' points to everybody, you included. Thanks for your comprehension. One should choose only one account...
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.