TRKNIGHT - Travelling Knight

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?

Input

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

Output

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

Example

Input:
3
2 1
2 2
3 3

Output:
1
5
7

Constraints

1 <= T <= 20
2 <= n <= 12
1 <= k <= 1000000000


Added by:Varun Jalan
Date:2010-01-25
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS OBJC PERL6 SQLITE VB.NET
Resource:own problem used for Codechef Snackdown Onsite

hide comments
2014-05-29 16:18:36 Francky
Python3 validator (by Francky) : OK ;-)
@Varun Jalan : your problems are awesome, and constraints are perfect. I found that m=1000007, n=12 is a first tricky case. (I don't know yet why, but it makes this problem rocks). Great kudos for all your work.
I'll try Py2.7... (fail, unless include lot of hardcoded materials)

Last edit: 2014-05-29 18:17:28
2011-06-29 21:21:06 Hagen von Eitzen
@ukasuevoli: don't forget the move sequence of length 0<k that simply stays in the initial corner
2011-06-28 12:38:23 ulasuevoli
@varun ! How the answer for second case =5 ?
2010-02-01 08:12:40 ~ adieus ~
need some hints ... should it be done with (A.M.)^K ?
2010-01-31 05:11:46 [Rampage] Blue.Mary
Er, seems that it needs ~6 seconds on my PC for only one test case if multiplying 150 size matrices...
2010-01-30 11:04:53 Ivan Katanic
maybe you're right, it just seemed to me that it can be solved with fft...btw, multiplying 150 size matrices isn't enough?

Last edit: 2010-01-30 11:05:19
2010-01-30 05:11:48 Varun Jalan
yes, in fact I do not know how to do it using FFT :D
2010-01-28 15:51:44 Ivan Katanic
is that problem solvable without using FFT and such things(yes/no)? or that is the only way...
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.