영구 운동 (라지)

레밍 공장의 바닥은 R x C 격자로 나뉘어 있다. 각 칸에는 컨베이어 벨트가 하나씩 놓여 있고, 벨트의 방향은 상하, 좌우, 두 대각선 가운데 하나다. 벨트는 자기 방향을 따라 앞이나 뒤로 움직이며, 어느 쪽으로 움직일지는 칸마다 따로 정한다.

지금은 각 칸의 한가운데에 레밍이 한 마리씩 서 있다. 벨트를 켜면 레밍은 자기가 선 칸의 벨트가 움직이는 방향으로 이동해 이웃한 칸의 한가운데까지 간다. 이 이동은 모두 동시에 일어나고 정확히 1초가 걸린다. 1초가 지나면 레밍은 모두 새 칸에 서 있고, 같은 일이 다시 시작된다. 벨트를 끄기 전까지 이 과정은 영원히 반복된다.

• 레밍이 새 칸에 들어서면 그 칸의 한가운데에 닿을 때까지 원래 가던 방향으로 계속 간다. 다음 1초가 시작되기 전까지는 새 칸의 벨트에 영향을 받지 않는다.
• 레밍이 격자 밖으로 나가면 반대편의 같은 위치로 들어온다. 예를 들어 맨 왼쪽 위 칸에서 왼쪽 위 대각선으로 움직이면 맨 오른쪽 아래 칸에 도착한다. 이 이동도 1초 만에 끝난다.
• 레밍끼리는 부딪히지 않고 서로 지나칠 수 있다.

두 레밍이 같은 순간에 같은 칸의 한가운데에 있으면 그때부터 둘은 붙어 다니게 된다. 그런 일이 한 번도 일어나지 않도록 벨트마다 움직일 방향을 정하는 것이 목표다.

위 예시에서 벨트의 방향을 정하는 방법 두 가지는 다음과 같다.

두 방법 모두 어떤 두 레밍도 같은 칸의 한가운데에 동시에 도착하지 않는다.

바닥 배치가 주어질 때, 어떤 두 레밍도 같은 칸의 한가운데에 동시에 있지 않도록 각 벨트의 방향을 정하는 방법의 수 N을 구하라. 답이 매우 클 수 있으므로 1000003으로 나눈 나머지를 출력한다.

첫 줄에 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 줄에는 양의 정수 R과 C가 주어진다.

그다음 R개의 줄에는 |, -, /, \ 네 문자로만 이루어진 길이 C의 문자열이 한 줄씩 주어진다. 각 문자는 그 칸에 놓인 벨트의 방향을 뜻한다.

• |는 위나 아래로 움직이는 벨트다.
• -는 왼쪽이나 오른쪽으로 움직이는 벨트다.
• /는 오른쪽 위나 왼쪽 아래로 움직이는 벨트다.
• \는 왼쪽 위나 오른쪽 아래로 움직이는 벨트다.

제한

• 1 ≤ T ≤ 25
• 3 ≤ R ≤ 100
• 3 ≤ C ≤ 100

각 테스트 케이스마다 "Case #x: M" 형식으로 한 줄씩 출력한다. x는 1부터 시작하는 테스트 케이스 번호이고, M은 N을 1000003으로 나눈 나머지다.