Bạn đã bao giờ đến Nhà máy Google Lemming chưa? Đó là một nơi rất khác thường. Sàn nhà được sắp xếp thành một lưới \(R \times C\). Trong mỗi ô vuông của lưới, có một băng chuyền định hướng theo chiều dọc (lên-xuống), chiều ngang (trái-phải), hoặc dọc theo một trong hai đường chéo. Các băng chuyền di chuyển tiến hoặc lùi dọc theo định hướng của chúng, và bạn có thể độc lập chọn một trong hai hướng di chuyển có thể cho mỗi băng chuyền.

Hiện tại, có một con lemming (chuột đồng) đang đứng ở trung tâm của mỗi ô vuông. Khi bạn khởi động các băng chuyền, mỗi con lemming sẽ di chuyển theo hướng của băng chuyền mà nó đang đứng cho đến khi nó đến trung tâm của một ô vuông mới. Tất cả các chuyển động này diễn ra đồng thời và mất đúng một giây để hoàn thành. Sau đó, tất cả các con lemming sẽ ở trên các ô vuông mới, và quá trình này sẽ lặp lại từ các vị trí mới của chúng. Điều này tiếp tục mãi mãi, hoặc ít nhất là cho đến khi bạn tắt các băng chuyền.

• Khi một con lemming đi vào một ô vuông mới, nó tiếp tục đi theo hướng mà nó đang đi cho đến khi nó đến trung tâm của ô vuông đó. Nó sẽ không bị ảnh hưởng bởi băng chuyền mới cho đến khi giây tiếp theo bắt đầu.
• Nếu một con lemming di chuyển ra khỏi mép của lưới, nó sẽ quay trở lại ở cùng một vị trí ở phía đối diện. Ví dụ, nếu nó di chuyển chéo lên và sang trái từ ô trên cùng bên trái, nó sẽ đến ô dưới cùng bên phải. Nhờ phép màu của khoa học, toàn bộ quá trình này vẫn chỉ mất 1 giây.
• Các con lemming không bao giờ va chạm và luôn có thể đi ngang qua nhau mà không gặp khó khăn.

Mẹo là chọn hướng cho mỗi băng chuyền sao cho các con lemming sẽ tiếp tục di chuyển mãi mãi mà không bao giờ có hai con kết thúc ở trung tâm của cùng một ô vuông tại cùng một thời điểm. Nếu điều đó xảy ra, chúng sẽ bị dính vào nhau từ đó về sau, và điều đó không vui vẻ gì cho chúng.

Dưới đây là hai cách gán hướng cho mỗi băng chuyền từ ví dụ trước:

Trong cả hai trường hợp, chúng ta tránh được việc gửi hai con lemming đến trung tâm của cùng một ô vuông tại cùng một thời điểm.

Cho một sơ đồ sàn tùy ý, hãy tính \(N\), số cách chọn hướng cho mỗi băng chuyền sao cho không bao giờ có hai con lemming kết thúc ở trung tâm của cùng một ô vuông tại cùng một thời điểm. Kết quả có thể rất lớn, vì vậy hãy xuất nó theo modulo \(1000003\).

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ test, \(T\). \(T\) bộ test tiếp theo. Mỗi bộ bắt đầu bằng một dòng chứa các số nguyên dương \(R\) và \(C\).

Tiếp theo là \(R\) dòng, mỗi dòng chứa một chuỗi gồm \(C\) ký tự được chọn từ "|-/\". Mỗi ký tự đại diện cho định hướng của băng chuyền trong một ô vuông:

• '|' đại diện cho băng chuyền có thể di chuyển lên hoặc xuống.
• '-' đại diện cho băng chuyền có thể di chuyển sang trái hoặc sang phải.
• '/' đại diện cho băng chuyền có thể di chuyển lên-phải hoặc xuống-trái.
• '\' đại diện cho băng chuyền có thể di chuyển lên-trái hoặc xuống-phải.

Dữ liệu ra

Đối với mỗi bộ test, hãy xuất một dòng chứa "Case #x: \(M\)", trong đó x là số thứ tự bộ test (bắt đầu từ 1) và \(M\) là phần dư khi chia \(N\) cho \(1000003\).

Ràng buộc

• \(1 \le T \le 25\).

Phân nhóm

• Test set 1 (Visible): \(3 \le R \le 4\); \(3 \le C \le 4\).
• Test set 2 (Hidden): \(3 \le R \le 100\); \(3 \le C \le 100\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

3
3 3
|-/
|||
--|
3 4
----
||||
\\//
4 4
|---
\-\|
\|||
|--\

Case #1: 2
Case #2: 0
Case #3: 16

Nguồn

Google Code Jam 2011, Vòng 3, bài Perpetual Motion.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.