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?

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

Input:
3
2 1
2 2
3 3

Output:
1
5
7

Constraints

1 <= T <= 20
2 <= n <= 12
1 <= k <= 1000000000