SP5975 TRKNIGHT - Travelling Knight
Description
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
Input Format
N/A
Output Format
N/A