Travelling KnightProblem code: SNON05 |
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.
Sample Input :
3 2 1 2 2 3 3
Sample Output :
1 5 7
Constraints :
1 <= T <= 20
2 <= n <= 12
1 <= k <= 1000000000
| Author: | fctrl |
| Date Added: | 28-12-2009 |
| Time Limit: | 7 sec |
| Source Limit: | 50000 Bytes |
| Languages: | ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TEXT, WSPC |
Comments
SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:
Fetching successful submissions
What it means by a corner
What it means by a corner here? The 4 corners(0, 0), (0, 2n-1), (2n-1,0), (2n-1, 2n-1) only?
Yeah, that is right.
Yeah, that is right.