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
hide comments
Francky:
2014-05-29 16:18:36
Python3 validator (by Francky) : OK ;-)
|
|
Hagen von Eitzen:
2011-06-29 21:21:06
@ukasuevoli: don't forget the move sequence of length 0<k that simply stays in the initial corner |
|
ulasuevoli:
2011-06-28 12:38:23
@varun ! How the answer for second case =5 ?
|
|
~ adieus ~:
2010-02-01 08:12:40
need some hints ... should it be done with (A.M.)^K ? |
|
[Rampage] Blue.Mary:
2010-01-31 05:11:46
Er, seems that it needs ~6 seconds on my PC for only one test case if multiplying 150 size matrices... |
|
Ivan Katanic:
2010-01-30 11:04:53
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 |
|
Varun Jalan:
2010-01-30 05:11:48
yes, in fact I do not know how to do it using FFT :D |
|
Ivan Katanic:
2010-01-28 15:51:44
is that problem solvable without using FFT and such things(yes/no)? or that is the only way... |
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 |