2048

2048이라는 게임이 있다. 이 게임은 $4\times 4$ 격자판 위에 $1 \times 1$ 크기의 조각이 놓여 있고, 방향키를 누르면 같은 수가 적힌 조각을 모두 그 방향으로 이동해 합칠 수 있다. 한 번 이동할 때마다 임의의 위치에 $2^{1}$부터 $2^{16}$까지의 $2$의 거듭제곱인 수가 적힌 타일이 생성된다. 격자판이 가득 차 있고 조각을 합치지 못하는 상황이 오면 게임이 종료된다.

유능한 해커이지만 2048에는 그리 능숙하지 않은 협이는 이 게임에서 $2^{17}$ 타일을 만들고 싶어졌다. 격자판이 $2^{17}$을 담기에 너무 좁다고 생각한 협이는 해킹 실력을 발휘해 가로 크기를 $w$, 세로 크기를 $h$로 바꾸어 게임을 했다. 그럼에도 협이는 $2^{17}$ 타일을 만드는 데 번번이 실패했다.

협이는 $2^{16}$ 타일 두 개를 한 번 합치는 것도 못하냐는 도훈이의 핀잔에, 게임이 끝나는 경우의 수가 너무 많아서 어쩔 수 없다고 주장하려 했다. 그러나 격자판의 가로 크기 $w$가 너무 커진 나머지, 협이는 경우의 수를 계산하기 어려워하고 있다. 협이를 대신해 게임이 종료되었을 때 격자판의 최종 상태로 가능한 경우의 수를 구해보자. 최종 상태란 인접한 칸에 같은 숫자가 적혀 있지 않으면서, 모든 칸에 $16$가지 중 하나의 타일이 존재하는 상태를 말한다.

첫째 줄에 질의의 개수 $Q$가 주어진다. $(1 \leq Q \leq 1\,000)$

두 번째 줄부터 $Q$개의 줄에 걸쳐 각 줄에 격자판의 크기 $h_i$와 $w_i$가 공백으로 구분되어 주어진다. $(1 \leq h_i \leq 6; 1 \leq w_i \leq 10^{18})$

각 질의에 대해, 최종 상태로 가능한 경우의 수를 $1\,000\,000\,007$으로 나눈 나머지를 한 줄에 하나씩 순서대로 출력한다.