Perpetual Motion (Small)

The floor of the lemming factory is divided into an $R \times C$ grid. Every square holds one conveyor belt, and the belt is oriented up-down, left-right, or along one of the two diagonals. A belt moves either forwards or backwards along its orientation, and you choose which of the two directions each belt moves in, independently for every square.

Right now one lemming stands at the center of every square. When you start the belts, each lemming moves in the direction of the belt he is standing on until he reaches the center of a new square. All these movements happen at the same time and take exactly one second. Afterwards every lemming stands on a new square and the same process repeats from there. The process runs forever unless you turn the belts off.

• When a lemming enters a new square, he keeps going in the direction he was already going until he reaches the center of that square. The belt in the new square affects him only from the start of the next second.
• If a lemming moves off the edge of the grid, he comes back at the same position on the opposite side. For example, moving diagonally up and left from the top-left square lands him on the bottom-right square. That movement also takes one second.
• Lemmings never collide and can always move past each other.

Your task is to choose a direction for every belt so that no two lemmings ever reach the center of the same square at the same moment. Once that happens, the two lemmings stay stuck together and move as one from then on.

Here are two ways of choosing the directions for the layout above.

Neither way ever sends two lemmings to the center of the same square at the same moment.

Given a floor layout, compute $N$, the number of ways to choose a direction for every belt so that no two lemmings ever reach the center of the same square at the same moment. $N$ can be very large, so print the remainder of $N$ divided by $1000003$.

The first line contains the number of test cases $T$. $T$ test cases follow. The first line of each test case contains the positive integers $R$ and $C$.

The next $R$ lines each contain a string of $C$ characters chosen from |, -, /, \. Each character gives the orientation of the belt in one square.

• | is a belt that moves up or down.
• - is a belt that moves left or right.
• / is a belt that moves up-right or down-left.
• \ is a belt that moves up-left or down-right.

Limits

• $1 \le T \le 25$
• $3 \le R \le 4$
• $3 \le C \le 4$

For each test case, print one line containing Case #x: M, where x is the test case number starting from 1 and $M$ is the remainder of $N$ divided by $1000003$.