드럼 장식하기 (스몰)

문제

당신은 록 밴드 Denise and the Integers의 드러머다. 드럼은 원기둥이고, 옆면은 직사각형 격자 모양의 칸으로 덮여 있다.

밴드는 매쓰랜드에서 공연한다. 매쓰랜드 관객은 까다로워서 드럼의 모든 칸에 양의 정수가 하나씩 적혀 있기를 요구한다. 0이나 음수는 적을 수 없다. 또 어떤 칸에 적힌 수가 $K$ 이면 그 칸은 같은 수 $K$ 가 적힌 칸과 정확히 $K$ 개 맞닿아야 한다. 맞닿는다는 것은 변을 공유한다는 뜻이고, 꼭짓점만 만나는 경우는 세지 않는다. 즉 1이 적힌 칸은 1이 적힌 칸 하나와 맞닿고, 2가 적힌 칸은 2가 적힌 칸 두 개와 맞닿는다. 이 조건만 지키면 나머지 이웃 칸에 어떤 수가 적혀 있든 상관없다.

드럼의 위아래 원판은 칸이 아니므로 장식하지 않는다. 그래서 맨 위 행과 맨 아래 행의 칸은 이웃이 셋이고, 나머지 칸은 이웃이 넷이다. 옆면은 원기둥을 한 바퀴 감고 있으므로 첫 번째 열과 마지막 열도 서로 맞닿는다.

예를 들어 행이 3개, 열이 5개인 격자를 감은 드럼에서 다음은 조건을 만족하는 장식이다.

행 3개와 열 5개짜리 드럼에 위 두 행은 3, 아래 한 행은 2를 적은 장식

(보이지 않는 뒤쪽 두 열도 보이는 세 열과 똑같다고 생각하면 된다.)

조건을 만족하는 장식이 몇 가지인지 세려고 한다. 원기둥의 대칭축을 중심으로 회전해서 한쪽을 다른 쪽으로 만들 수 없을 때 두 장식은 서로 다르다. 드럼의 위와 아래는 구분하므로 다음 장식은 위의 장식과 다른 장식이다.

행 3개와 열 5개짜리 드럼에 위 한 행은 2, 아래 두 행은 3을 적은 장식

(이 그림에서도 뒤쪽 두 열은 보이는 세 열과 똑같다.)

드럼은 행이 $R$ 개, 열이 $C$ 개다. 서로 다른 장식은 모두 몇 가지인가? 개수를 $10^9+7$ 로 나눈 나머지를 구하라.

입력

첫 줄에 테스트 케이스의 개수 $T$ 가 주어진다. 이어지는 $T$ 개의 줄에는 각각 드럼의 행 개수 $R$ 과 열 개수 $C$ 가 공백을 사이에 두고 주어진다.

제한

$1 \le T \le 20$
$2 \le R \le 6$
$3 \le C \le 6$

출력

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$ 는 1부터 시작하는 테스트 케이스 번호이고, $y$ 는 조건을 만족하는 장식의 개수를 $10^9+7$ 로 나눈 나머지다.

힌트

$R=2$ , $C=4$ 인 드럼에서는 모든 칸에 3을 적는 장식 하나뿐이다. $R=3$ , $C=5$ 인 드럼에서는 위 그림에 나온 두 가지뿐이다.