Statement:

Your task is simple. A knight is placed on the top left corner of a chessboard having 2*n* rows and 2*n* 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 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 <= 10^{9}

Time and memory limit:

- 1s
- 512MB

**Problem source:** Sphere Online Judge