드럼 장식가

당신은 록 밴드 Denise와 정수들의 드러머이다. 당신의 드럼은 직사각형 격자의 칸들을 둘러 감은 원기둥이다.

당신의 밴드는 Mathland에서 공연할 예정이다. Mathland 사람들은 까다로운 관객이며, 드럼의 모든 칸에 양의 정수가 들어 있기를 기대한다. 영과 음의 정수는 허용되지 않는다. 또한 각 정수 K는 같은 정수가 적힌 다른 칸 정확히 K개와 변을 맞대야 한다(점만 공유해서는 안 된다). 즉, 1이 적힌 칸은 1이 적힌 다른 칸 정확히 하나와 맞닿아야 하고, 2이 적힌 칸은 2이 적힌 다른 칸 정확히 2개와 맞닿아야 하며, 이후도 같은 방식이다. 이 제한을 제외하면, 한 칸이 어떤 다른 칸들과 맞닿는지는 중요하지 않다. (드럼의 원형 윗면과 아랫면은 칸으로 간주하지 않으며 장식할 필요도 없다. 따라서 드럼의 맨 위와 맨 아래에 있는 칸들은 각각 다른 칸 세 개와만 맞닿지만, 그 밖의 모든 칸은 각각 다른 칸 네 개와 맞닿는다.)

예를 들어, 다음은 3개의 행과 5개의 열로 이루어진 격자로 만든 원기둥의 올바른 장식이다. (드럼 뒤쪽에 보이지 않는 두 열은 보이는 세 열과 같다고 상상하라.)

서로 다른 올바른 장식이 몇 가지 가능한지 알고 싶다. 원기둥의 대칭축을 중심으로 한 장식을 회전시켜 다른 장식을 만들 수 없다면 두 장식은 서로 다르다. 드럼의 윗면과 아랫면은 서로 다른 것으로 간주하므로, 3x5 격자의 다음 장식은 위의 장식과 다르다. (마찬가지로, 드럼 뒤쪽에 보이지 않는 두 열은 보이는 세 열과 같다고 상상하라.)

드럼에는 R개의 행과 C개의 열이 있다. 서로 다른 올바른 장식은 몇 가지 가능한가? 그 수는 클 수 있으므로, 장식의 수를 $10^{9}$ + 7 (1000000007)로 나눈 나머지를 반환한다.

제한

메모리 제한: 1 GB.

작은 데이터 세트

시간 제한: 240초. 1 ≤ T ≤ 20. 2 ≤ R ≤ 6. 3 ≤ C ≤ 6.

큰 데이터 세트

시간 제한: 480초. 1 ≤ T ≤ 100. 2 ≤ R ≤ 100. 3 ≤ C ≤ 100.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 줄이 주어지며, 각 줄에는 드럼의 행 수와 열 수를 나타내는 두 정수 R과 C가 공백으로 구분되어 주어진다.

각 테스트 케이스마다 "Case #x: y"를 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이며(1부터 시작한다), y는 위에서 설명한 올바른 장식의 수를 $10^{9}$ + 7로 나눈 나머지이다.

케이스 #1에서는 모든 칸을 3로 채우는 것이 유일한 해이다.

케이스 #2에서는 문제 설명의 그림에 나온 두 가지가 유일한 해이다.