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 at most 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.


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

hide comments
2020-08-09 13:20:23 suhash
Amazing problem (learnt something new). Thanks a lot @Francky! :)

=(Francky)=> You're welcome!

Last edit: 2020-08-09 22:58:47
2020-04-03 11:10:22 Alexander Rass
Can anyone give a hint on this question. I am fighting with this task for years...
Any help is appreciated. Thank you.
I solved TRKNIGHT very fast (0.02s).
EDIT:
Finally solved the task. I think a hint on the needed theorem would be very helpful to get at least an idea how to solve it. I suggest to add such a hint here but as I am not the author I will not do this.

=(Francky)=> I'm the author and I won't do it too. A moto from project Euler : "If you can't solve it, then you can't solve it!"

Last edit: 2020-04-04 10:32:35
2017-09-11 20:26:33 [Rampage] Blue.Mary
It's quite a long way to get a desired solution...
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
2014-06-02 19:22:08 Min_25
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
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.