{"code":"22thtbc5","name":"Robot","description":"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 dưới, các cột đượ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$) được gọi là ô $(u,v)$. Mỗi ô của bảng sẽ có chỉ dẫn cho bước đi tiếp theo của robot.\r\n\r\nVí dụ, bảng dưới là một ví dụ:\r\n\r\n![enter image description here][1]\r\n\r\n - Robot ban đầu ở vị trí $(1,1)$, bước tiếp theo robot sẽ di chuyển sang phải tới ô $(1,2)$.\r\n - Ở ô $(1,2)$, robot nhận chỉ dẫn di chuyển tiếp xuống dưới là ô $(2,2)$.\r\n - Ở ô $(2,2)$, robot nhận chỉ dẫn di chuyển tiếp xuống dưới là ô $(3,2)$.\r\n - Ở ô $(3,2)$, robot nhận chỉ dẫn di chuyển lên trên là ô $(2,2)$.\r\n - Robot sẽ di chuyển giữa hai ô $(2,2)$ và $(3,2)$.\r\n\r\nMinh muốn thử nghiệm đưa robot di chuyển từ ô $(x_s,y_s)$ tới được ô $(x_t,y_t)$ nhưng bảng hướng dẫn có thể không làm cho robot di chuyển được như vậy. Bạn được quyền thay đổi hướ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ừ $(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. Trường hợp không cần thay đổi ô nào thì số cách là $1$. Ngược lại, hai cách thay đổi được coi là khác nhau nếu một trong hai điều sau xảy ra:\r\n\r\n - Tồn tại một ô được thay đổi trong cách thứ nhất mà không được thay đổi trong cách thứ hai.\r\n - Tồn tại một ô dượ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.\r\n\r\n#### Input\r\n\r\n - Dòng đầu chứa ba số $R,C$ và $q$, trong đó $R,C$ là kích thước của bảng và $q$ là số trường hợp thử nghiệm.\r\n - 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 bốn kí tự `U`, `D`, `L`, `R` tương ứng với đi lên trên, xuống dưới, sang trái, sang phải.\r\n - $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.\r\n\r\n#### Output\r\n\r\n - 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)$.\r\n\r\n#### Scoring\r\n\r\n - Subtask $1$ ($15\\%$ số điểm): $R,C \\le 4, q \\le 3$.\r\n - Subtask $2$ ($15\\%$ số điểm): $R = 1, q \\le 3$.\r\n - Subtask $3$ ($20\\%$ số điểm): $R,C \\le 100, q \\le 3$.\r\n - Subtask $4$ ($20\\%$ số điểm): $R,C \\le 1000, q \\le 3$.\r\n - Subtask $5$ ($10\\%$ số điểm): $R,C \\le 1000, q \\le 10$.\r\n - Subtask $6$ ($20\\%$ số điểm): $R \\times C \\le 10^6, q \\le 10$.\r\n\r\n#### Example\r\n\r\n???+ question \"Test 1\"\r\n    ???+ \"Input\"\r\n        ```sample\r\n        3 4 2\r\n        RDRD\r\n        RDRD\r\n        UUUL\r\n        1 1 3 2\r\n        1 1 3 4\r\n        ```\r\n        \r\n    ???+ success \"Output\"\r\n        ```sample\r\n        0 1\r\n        1 3\r\n        ```\r\n        \r\n    ??? warning \"Note\"\r\n        - Trường hợp đầu tiên, không cần thay đổi chỉ dẫn nào.\r\n        - Trường hợp thứ hai, chỉ cần thay đổi $1$ ô bằng $1$ trong $3$ cách sau:\r\n            + ô $(1,2)$ từ `D` sang `R`.\r\n            + ô $(2,2)$ từ `D` sang `R`.\r\n            + ô $(3,2)$ từ `U` sang `R`.\r\n            \r\n???+ question \"Test 2\"\r\n    ???+ \"Input\"\r\n        ```sample\r\n        2 2 1\r\n        UD\r\n        RR\r\n        1 1 2 2\r\n        ```\r\n        \r\n    ???+ success \"Output\"\r\n        ```sample\r\n        1 2\r\n        ```\r\n        \r\n    ??? warning \"Note\"\r\n        Thay đổi chỉ dẫn ô $(1,1)$ từ `U` thành `R` hoặc `D` đều có thể đưa robot đến đích.\r\n\r\n  [1]: https://cdn.lqdoj.edu.vn/media/pagedown-uploads/451627783_1183878119321119_7137375906381279171_n.png","points":2400.0,"partial":true,"time_limit":1.0,"memory_limit":1048576,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}