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 ?
The first line contains an integer T, the number of test cases. Each of the next T lines contains 2 integers : n, k.
Output T lines, one for each test case, containing the required total number of configurations. Since the answer can get very big, output it modulo 1000007.
3 2 1 2 2 3 3
1 5 7
1 <= T <= 100 2 <= n <= 24 1 <= k <= 109
Problem source: Sphere Online Judge