Travelling Knight

Statement:

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 ?

knight

Input

The first line contains an integer T, the number of test cases. Each of the next T lines contains 2 integers : n, k.

Output

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.

Example input:
3
2 1
2 2
3 3
Example output:
1
5
7

Constraints

1 <= T <= 100
2 <= n <= 24
1 <= k <= 109
Time and memory limit:

  • 1s
  • 512MB

Problem source: Sphere Online Judge