Robot (Bài 3 bảng C2, Bài 2 bảng C1)

Minh mới tạo ra một robot có khả năng nhận dạng trên sàn và di chuyển theo các chỉ dẫn đó. Sàn là một bảng gồm \(R\) hàng và \(C\) cột. Các hàng được đánh số từ 1 đến \(R\) từ trên xuống duới, các cột đuợc đánh số từ 1 đến \(C\) từ trái sang phải. Ô ở hàng thứ \(u\ (1 \le u \le R)\) và cột thứ \(v\ (1 \le v \le C)\) đuợc gọi là ô (u,v). Mồi ô của bảng sẽ có chỉ dẫn cho buớc đi tiếp theo cho robot.

Ví dụ, bảng phía dưới là một ví dụ.

• Robot ban đầu ở vị trí ô (\(1,1\)), buớc tiếp theo robot sẽ di chuyển sang phải tới ô (\(1, 2\)).
• Ở ô (\(1, 2\)), robot nhận chỉ dẫn di chuyển tiếp xuống duới là ô (\(2, 2\)).
• Ở ô (\(2, 2\)), robot nhận chỉ dẫn di chuyển tiếp xuống duới là ô (\(3, 2\)).
• Ở ô (\(3, 2\)), robot nhận chỉ dẫn di chuyển lên trên là ô (\(2, 2\)).
• Robot sẽ di chuyển giữa hai ô (\(2, 2\)) và (\(3, 2\)).

Minh muốn thử nghiệm đua robot di chuyển từ ô (\(x_s, y_s\)) tới đuợc ô (\(x_t, y_t\)) nhung bảng huớng dẫn có thể không làm cho robot di chuyển đuợc nhu vậy. Bạn đuợc quyền thay đồi huớng dẫn của một số ô để robot có thể đi từ (\(x_s,y_s\)) đến (\(x_t,y_t\)). Nhiệm vụ của bạn là chọn ít nhất các ô và thay đổi chỉ dẫn của các ô này để robot có thể đi từ đi từ (\(x_s,y_s\)) đến (\(x_t,y_t\)). Nếu có nhiều cách thay đổi chỉ dẫn các ô, hãy đếm số cách thay đổi khác nhau. Truờng hợp không cần thay đổi ô nào thì số cách là 1. Nguợc lại, hai cách thay đổi đuợc coi là khác nhau nếu một trong hai điều sau xảy ra:

• Tồn tại một ô được thay đồi trong cách thứ nhất mà không đuợc thay đổi trong cách thứ hai.
• Tồn tại một ô được thay đổi trong cả hai cách, nhưng chỉ dẫn sau khi thay đồi ở cách thứ nhất khác cách thứ hai.

Input

• Dòng đầu chứa ba số \(R, C\) và \(q\), trong đó \(R, C\) là kích thuớc của bảng và \(q\) là số truờng hợp thứ nghiệm;
• Tiếp theo là \(R\) dòng, mỗi dòng chửa xâu kí tụ độ dài \(C\). Kí tụ thứ \(v\) trên dòng thứ \(u\), thể hiện chỉ dẫn của ô (\(u, v\)). Chỉ dẫn thuộc một trong 4 kí tự \(U, D, L, R\) tương ứng với đi lên trên, xuống duới, sang trái, sang phải;
  • \(q\) dòng cuối, mỗi dòng chứa bốn số nguyên \(x_s, y_s, x_t, y_t\) tương ứng với một thử nghiệm.

Output

• Ghi ra gồm \(q\) dòng, mỗi dòng gồm hai số cách nhau một dấu cách: số thứ nhất ghi ra số ô phải thay đổi ít nhất, số thứ hai là phần dư trong phép chia số cách thay đổi khác nhau chia cho (\(10^9 + 7\)).

Scoring

• Subtask \(1\) (\(15\%\) số điểm): \(R, C \le 4; q \le 3\);
• Subtask \(2\) (\(15\%\) số điểm): \(R = 1; q \le 3\);
• Subtask \(3\) (\(20\%\) số điểm): \(R,C \le 100; q \le 3\);
• Subtask \(4\) (\(20\%\) số điểm): \(R,C \le 1000; q \le 3\);
• Subtask \(5\) (\(10\%\) số điểm): \(R,C \le 1000; q \le 10\);
• Subtask \(6\) (\(20\%\) số điểm): \(R \times C \le 10^6; q \le 10\);

Example

3 4 2
RDRD
RDRD
UUUL
1 1 3 2 
1 1 3 4 

0 1
1 3

2 2 1
UD
RR
1 1 2 2 

1 2