34674번 - 타카하시의 기차 퍼즐 놀이 2

문제

타카하시는 컴퓨터로 기차 퍼즐 게임을 하고 있었습니다. 반복된 퍼즐 게임에 질렸던 타카하시는 여러분들에게 다음과 같은 질문을 하였습니다.

[그림 1] 왼쪽 위부터 시계 방향으로 1ドル$번, 2ドル$번, 4ドル$번, 3ドル$번 블록

[그림 2] 덮이지 않는 공간이 하나 이상 있는 경우

세로 길이가 $r$이고 가로 길이가 $c$인 직사각형 모양의 퍼즐이 있어. 퍼즐에는 1ドル$번부터 4ドル$번까지 회전할 수 없는 4ドル$가지 블록이 있고, 각 블록은 제한 없이 쓸 수 있어. 블록들을 퍼즐 영역 내부에 빈틈없이 채우려고 해. 퍼즐 영역이 커진다면, 채울 수 있는 가짓수가 많아지겠지? 4ドル$가지 블록들을 적절히 사용해서 퍼즐 영역 내부를 빈틈없이 채울 수 있는 가짓수를 10ドル^{9}+7$로 나눈 나머지를 구해 줘.

타카하시의 질문을 해결해 주세요.

입력

첫 번째 줄에 $Q$가 주어집니다.

두 번째 줄부터 $Q$개의 줄에 걸쳐 $r,ドル $c$가 공백으로 구분되어 주어집니다.

출력

$Q$개의 줄에 걸쳐 문제의 답을 아래와 같이 한 줄에 하나씩 출력해 주세요.

제한

• 1ドル \leq Q \leq 10^{6}$
• 1ドル \leq r \leq 6$이고 $r$은 짝수입니다.
• 1ドル \leq c \leq 10^{6}$

노트