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 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
Output:
1
5
7

Constraints

1 <= T <= 50
2 <= n <= 24
1 <= k <= 10^9

Information

In the input files, there will be two cases for each possible n.
Constraints allows fast languages to get AC under 0.5s (total time for the 5 input files), with non-optimized scholar methods only. Advanced methods can be slightly faster, and needed to get AC with interpreted languages (without any guaranty for all of them).
It is recommended to solve first the original problem TRKNIGHT in a very fast way. After that, solve this problem could remain a hard task ; it's not just a simple extension.
Good luck and have fun ;-)

Edit(12/II/2017, compiler update) New TL.