## 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 1Output: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.

hide comments

Francky:
2014-03-29 08:07:41
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... |

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 |