영구 운동

Google Lemming Factory에 가 본 적이 있는가? 그곳은 매우 특이한 장소이다. 바닥은 R x C 격자로 배열되어 있다. 각 격자 칸에는 상하, 좌우 또는 두 대각선 중 하나의 방향으로 놓인 컨베이어 벨트가 있다. 컨베이어 벨트는 놓인 방향을 따라 정방향이나 역방향으로 움직이며, 각 컨베이어 벨트가 가능한 두 방향 중 어느 방향으로 움직일지 독립적으로 선택할 수 있다.

현재 각 칸의 중앙에는 레밍 한 마리가 서 있다. 컨베이어 벨트를 작동시키면 각 레밍은 자신이 올라선 컨베이어 벨트의 방향으로 움직여 새로운 칸의 중앙에 도달한다. 이 모든 이동은 동시에 일어나며 완료하는 데 정확히 일 초가 걸린다. 그 후 모든 레밍은 새로운 칸에 있게 되고, 새로운 위치에서 이 과정이 반복된다. 이는 영원히, 또는 적어도 컨베이어 벨트를 끌 때까지 계속된다.

• 레밍이 새로운 칸에 들어가면 그 칸의 중앙에 도달할 때까지 이미 가고 있던 방향으로 계속 이동한다. 다음 초가 시작되기 전까지는 새로운 컨베이어 벨트의 영향을 받지 않는다.

• 레밍이 격자의 경계 밖으로 이동하면 반대편의 같은 위치로 돌아온다. 예를 들어 왼쪽 위 칸에서 대각선 왼쪽 위로 이동한다면 오른쪽 아래 칸에 도착한다. 과학의 기적 덕분에 이 모든 과정에는 여전히 1초만 걸린다.

• 레밍들은 절대 충돌하지 않으며 언제나 아무 어려움 없이 서로를 지나갈 수 있다.

핵심은 어떤 때에도 두 레밍이 동시에 같은 칸의 중앙에 도달하지 않으면서 영원히 계속 움직이도록 각 컨베이어 벨트의 방향을 선택하는 것이다. 그런 일이 일어나면 그때부터 레밍들이 서로 붙어 버리는데, 이는 레밍들에게 그다지 재미있는 일이 아니다.

앞의 예제에서 각 컨베이어 벨트에 방향을 지정하는 두 가지 방법은 다음과 같다.

두 경우 모두 두 레밍을 동시에 같은 칸의 중앙으로 보내는 일을 영원히 피할 수 있다.

임의의 바닥 배치가 주어질 때, 어떤 두 레밍도 동시에 같은 칸의 중앙에 도달하는 일이 영원히 없도록 각 컨베이어 벨트의 방향을 선택하는 방법의 수 N을 계산한다. 답이 상당히 클 수 있으므로 1000003로 나눈 나머지를 출력한다.

제한

1 ≤ T ≤ 25. 메모리 제한: 1GB.

작은 데이터셋 (테스트 세트 1 - 공개)

3 ≤ R ≤ 4. 3 ≤ C ≤ 4. 시간 제한: 30초.

큰 데이터셋 (테스트 세트 2 - 비공개)

3 ≤ R ≤ 100. 3 ≤ C ≤ 100. 시간 제한: 60초.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 양의 정수 R과 C가 들어 있는 한 줄로 시작한다.

이어서 각각 "|-/\"에서 선택된 C개의 문자로 이루어진 문자열을 포함하는 R개의 줄이 주어진다. 각 문자는 한 칸에 있는 컨베이어 벨트의 방향을 나타낸다.

• '|'는 위나 아래로 움직일 수 있는 컨베이어 벨트를 나타낸다.

• '-'는 왼쪽이나 오른쪽으로 움직일 수 있는 컨베이어 벨트를 나타낸다.

• '/'는 오른쪽 위나 왼쪽 아래로 움직일 수 있는 컨베이어 벨트를 나타낸다.

• '\'는 왼쪽 위나 오른쪽 아래로 움직일 수 있는 컨베이어 벨트를 나타낸다.

각 테스트 케이스마다 "Case #x: M"를 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이며 1부터 시작하고, M은 N을 1000003로 나눈 나머지이다.