KN2 - Travelling Knight 2


Your task is simple. A knight is placed on the top left corner of a chessboard having 2n rows and 2n columns.
In how many ways can it move such that it ends up at a corner after atmost k moves ?

knight

Input

The first line contains an integer T, the number of test cases. Each of the next T lines contains 2 integers : n, k.

Output

Output T lines, one for each test case, containing the required total number of configurations.
Since the answer can get very big, output it modulo 1000007.

Example

Input:

3
2 1
2 2
3 3

Output:
1
5
7

Constraints

1 <= T <= 50
2 <= n <= 24
1 <= k <= 10^9

Information

In the input files, there will be two cases for each possible n.
Constraints allows fast languages to get AC under 0.5s (total time for the 5 input files), with non-optimized scholar methods only. Advanced methods can be slightly faster, and needed to get AC with interpreted languages (without any guaranty for all of them).
It is recommended to solve first the original problem TRKNIGHT in a very fast way. After that, solve this problem could remain a hard task ; it's not just a simple extension.
Good luck and have fun ;-)

Edit(12/II/2017, compiler update) New TL.


hide comments
[Rampage] Blue.Mary: 2017-09-11 20:26:33

It's quite a long way to get a desired solution...

ammen99: 2017-05-11 11:44:07

Are you sure this problem can be solved using non-optimized scholar methods(I don' t count fft as such, just matrices)? I'm using cpp14 and I have a pretty optimized solution, it works in 0.02 in the easier version, however I'm getting TL.
=(Francky)=> Yes, I'm sure. The problem was designed with that in mind.

Last edit: 2017-05-11 13:38:54
Min_25: 2014-06-02 19:22:08

Although I don't know whether my solution is an intended solution or not, I learned another fast computation technique. :)
Nice problem.
--ans(Francky)--> Congratulations. We shared the same time 0.83s ! ;-) Our codes are quite similar, with some differences. I too learned a new technique to create this problem. Congrats again. (I used 4.4MB of memory in C, twice more precomputed materials, not exactly the same as you, but the same spirit in methods)

Last edit: 2014-06-02 19:43:23

Added by:Francky
Date:2014-06-01
Time limit:0.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:TRKNIGHT