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 ?
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 nonoptimized 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:
20170911 20:26:33
It's quite a long way to get a desired solution... 

ammen99:
20170511 11:44:07
Are you sure this problem can be solved using nonoptimized 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.


Min_25:
20140602 19:22:08
Although I don't know whether my solution is an intended solution or not, I learned another fast computation technique. :)

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