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