Sphere Online Judge

SPOJ Problem Set (classical)

5975. Travelling Knight

Problem code: TRKNIGHT


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 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

Sample Input :
3
2 1
2 2
3 3

Sample Output :
1
5
7

Constraints


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


Added by:Varun Jalan
Date:2010-01-25
Time limit:6s
Source limit:50000B
Memory limit:256MB
Cluster: Pyramid (Intel Pentium III 733 MHz)
Languages:All except: NODEJS PERL 6
Resource:own problem used for Codechef Snackdown Onsite

hide comments
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 [Retired] 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 KataniŠ
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 KataniŠ
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.