2048

The game 2048 is played on a $4\times 4$ grid with $1 \times 1$ tiles. Pressing an arrow key moves every tile with the same number in that direction and merges them. After each move, a tile with a power of two from $2^{1}$ to $2^{16}$ appears at a random empty position. The game ends when the grid is full and no tiles can be merged.

Hyun is a skilled hacker but not a strong 2048 player. Hyun wanted to make a $2^{17}$ tile in this game. Thinking the $4\times 4$ grid was too narrow to hold $2^{17}$, Hyun used hacking skills to change the width to $w$ and the height to $h$ and played again. Even so, Hyun failed to make a $2^{17}$ tile every time.

When Dohoon teased Hyun for not being able to merge two $2^{16}$ tiles, Hyun tried to argue that there are too many possible ending positions to deal with. However, the width $w$ has grown so large that Hyun now finds it hard to count those positions. Compute the number of possible final states of the grid when the game ends, on Hyun's behalf. A final state is one where no two adjacent cells hold the same number and every cell holds one of the 16 possible tiles.

The first line contains the number of queries $Q$. $(1 \leq Q \leq 1\,000)$

From the second line on, each of the $Q$ lines contains the grid height $h_i$ and width $w_i$, separated by a space. $(1 \leq h_i \leq 6; 1 \leq w_i \leq 10^{18})$

For each query, print the number of possible final states modulo $1\,000\,000\,007$, one per line in order.