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:  20100125 
Time limit:  0.839s

Source limit:  50000B 
Memory limit:  1536MB 
Cluster: 
Cube (Intel Pentium G860 3GHz)

Languages:  All except: NODEJS PERL 6 SCM chicken VB.net 
Resource:  own problem used for Codechef Snackdown Onsite 
