Perpetual Motion (Large)

The floor of the lemming factory is an R x C grid. Every square holds one conveyor belt, oriented up-down, left-right, or along one of the two diagonals. A belt runs forwards or backwards along its orientation, and you choose the direction of each belt independently.

Right now one lemming stands at the center of each square. When the belts start, every lemming moves in the direction of the belt under him until he reaches the center of a neighboring square. All of these moves happen at the same time and take exactly one second. After that second the lemmings stand on new squares and the same thing happens again, forever, or at least until you turn the belts off.

• Once 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 of the new square does not affect him until the next second starts.
• A lemming who moves off the edge of the grid comes back at the same position on the opposite side. For example, moving up and left from the top-left square lands him on the bottom-right square. That move still takes one second.
• Lemmings never collide and can always move past each other.

If two lemmings ever reach the center of the same square at the same moment, they are stuck together from then on. Your goal is to pick a direction for every belt so that this never happens.

Here are two ways to pick directions for the layout above.

In both of them, no two lemmings ever reach the center of the same square at the same time.

Given a floor layout, count N, the number of ways to pick a direction for every belt so that no two lemmings are ever at the center of the same square at the same time. The answer can be very large, so print it modulo 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 taken from |, -, /, \. Each character is the orientation of the belt in that 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 ≤ T ≤ 25
• 3 ≤ R ≤ 100
• 3 ≤ C ≤ 100

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