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!
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.
For each test case, print the number of possibility to do the job, modulo 1000000007.
Input: 3 1 C 1 3 B 2 5 A 1 Output: 1 8 192
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.
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.
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...