나선형 행렬

리는 Google Developer Day 입장권을 받았다. 전시장에 도착해 보니 부스가 $n \times m$ 크기의 행렬 모양으로 놓여 있었다.

불행히도 리는 GDD 일주일 전 농구를 하다가 왼쪽 발목을 심하게 삐었다. 그래서 원하는 대로 자유롭게 돌아다닐 수 없다. 왼쪽으로 돌면 발목이 다시 다친다. 리는 오른쪽으로 여러 번 돌아 크게 한 바퀴 도는 모습도 보이고 싶지 않다.

리는 모든 부스를 정확히 한 번씩 방문하려고 한다. 발목 사정을 고려해 방문 규칙을 정했다. 리는 전시장의 어느 부스에서든 시작할 수 있고, 처음 향할 방향도 고를 수 있다. 이후 각 이동은 다음 두 가지 중 하나여야 한다.

1. 직진해서 다음 부스를 방문한다.
2. 오른쪽으로 한 번 돈 뒤 직진해서 다음 부스를 방문한다.

당신은 리의 친구이고 평소 그를 자주 돕는다. 모든 부스를 정확히 한 번씩 방문하는 서로 다른 방법의 수를 구하라. 두 방법은 방문 순서가 다를 때에만 서로 다른 방법으로 본다.

첫 줄에 테스트 케이스의 수 $T$ ($1 \le T \le 100$)가 주어진다. 이어서 $T$개의 테스트 케이스가 주어진다.

각 테스트 케이스는 한 줄이며, 두 정수 $n$과 $m$ ($1 \le n, m \le 100$)이 주어진다. 각각 행렬의 행 수와 열 수이다.

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. 여기서 $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 $10^9+7$로 나눈 나머지인 서로 다른 방법의 수이다.

$n = 2$, $m = 2$일 때 방법은 4가지이다.