드럼 장식 (Large)

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

밴드는 수학나라에서 공연한다. 수학나라 관객은 까다로워서 드럼의 모든 칸에 양의 정수가 하나씩 적혀 있기를 요구한다. 0과 음수는 쓸 수 없다. 또 어떤 칸에 적힌 정수 $K$는 같은 수 $K$가 적힌 칸과 정확히 $K$개 맞닿아야 한다. 여기서 맞닿는다는 것은 변을 공유한다는 뜻이고, 꼭짓점만 닿는 경우는 세지 않는다. 즉 1이 적힌 칸은 1이 적힌 칸 하나와만 맞닿고, 2가 적힌 칸은 2가 적힌 칸 둘과만 맞닿는다. 이 조건 말고는 이웃 칸에 어떤 수가 적혀 있어도 상관없다. 드럼의 위아래 원판은 칸이 아니므로 장식하지 않는다. 그래서 맨 윗줄과 맨 아랫줄의 칸은 각각 세 칸과 맞닿고, 나머지 칸은 네 칸과 맞닿는다.

예를 들어 다음은 3행 5열 격자로 만든 원기둥의 올바른 장식이다.

보이지 않는 뒤쪽 두 열도 보이는 세 열에서 이어진다고 생각하면 된다.

서로 다른 장식이 몇 가지인지 세려고 한다. 원기둥의 대칭축을 중심으로 아무리 돌려도 한 장식을 다른 장식에 포갤 수 없을 때, 두 장식은 서로 다르다. 드럼의 위와 아래는 구별하므로 아래의 $3 \times 5$ 장식은 위의 장식과 다르다.

이 그림에서도 보이지 않는 뒤쪽 두 열은 보이는 세 열에서 이어진다.

드럼은 $R$행 $C$열이다. 서로 다른 장식은 몇 가지인가? 답이 클 수 있으므로 $10^9 + 7$로 나눈 나머지를 구한다.

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

제한

• $1 \le T \le 100$
• $2 \le R \le 100$
• $3 \le C \le 100$

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

$R = 2$, $C = 4$이면 모든 칸을 3으로 채우는 방법 하나뿐이다.

$R = 3$, $C = 5$이면 방법이 두 가지뿐이고, 문제 설명에 실린 그림 두 개가 각각 그 하나씩이다.