{"code":"hsgtrjump","name":"Nhảy về đích (HSG11v2-2022)","description":"Xét bảng hình chữ nhật kích thước $m \\times n$ ô. Các hàng được đánh số từ $1$ đến $m$ từ trên xuống dưới, các cột được đánh số từ $1$ đến $n$ từ trái qua phải. Ô nằm trên hàng $i$ và cột $j$ được ghi một số nguyên không âm ký hiệu $c_{ij}$ .Ở góc trên trái bảng có một quân cờ. Ta phải chuyển quân cờ về ô dưới phải của bảng theo quy tắc sau:\r\n\r\n - Tại mỗi bước nhảy, chỉ được di chuyển sang phải trên cùng một hàng hoặc di chuyển xuống dưới theo cùng một cột\r\n - Kích thước bước nhảy không được vượt quá số ghi trên ô có quân cờ hiện tại\r\n - Chỉ được di chuyển trong phạm vi bảng đang xét\r\n\r\n\r\nKích thước của bước nhảy từ ô $(i,j)$ tới ô $(u, v)$ được tính bằng giá trị $u + v − i − j$.\r\n\r\n**Yêu cầu:** Cho dãy $a_1, a_2, ..., a_m, b_1, b_2,...,b_n$ và số nguyên dương $k$. Bảng $C$ kích thước $m \\times n$ được xác định với $C_{ij} = 1 + [(a_i + b_j)$ mod $k] \\forall i = 1 ÷ m; j = 1 ÷ n$. Hãy tính số lượng cách di chuyển quân cờ từ ô trên trái $(1,1)$ xuống ô dưới phải $(m, n)$.\r\n\r\n<h4>Input</h4>\r\n\r\nvào từ file văn bản JUMP.INP có cấu trúc như sau:\r\n- Dòng đầu chứa 3 số nguyên dương $m, n, k ( m, n, k \\le  4.10^3)$\r\n- Dòng thứ hai chứa $m$ số nguyên $a_1, a_2, a_3, ... , a_m (0 \\le  a_i \\le  10^9)$\r\n- Dòng thứ ba chứa $n$ số nguyên $b_1, b_2, b_3, ... , b_n (0 \\le  b_i \\le  10^9)$\r\n\r\n<h4>Output</h4>\r\n\r\n- Ghi ra file văn bản JUMP.OUT một số nguyên duy nhất là số cách di chuyển tìm\r\nđược lấy theo module $10^9 + 7$.\r\n\r\n<h4>Scoring</h4>\r\n\r\n- Subtask $1$ ($15\\%$ số điểm): $m, n \\le  10, k = 1$\r\n- Subtask $2$ ($15\\%$ số điểm): $m, n \\le  10^3, k = 1$\r\n- Subtask $3$ ($20\\%$ số điểm): $m, n \\le  10^3, k \\le  10$\r\n- Subtask $4$ ($20\\%$ số điểm): $m, n \\le  10^3$\r\n- Subtask $5$ ($30\\%$ số điểm): không có ràng buộc gì thêm\r\n\r\n<h4>Example</h4>\r\n\r\n!!! question \"Test 1\"\r\n\r\n    ???+ \"Input\"\r\n        ```sample\r\n        3 2 1\r\n        3 4 11\r\n        2 5\r\n        ```\r\n    \r\n    ???+ success \"Output\"\r\n        ```sample\r\n        3\r\n        ```\r\n    \r\n!!! question \"Test 2\"\r\n\r\n    ???+ \"Input\"\r\n        ```sample\r\n        3 2 2\r\n        3 4 11\r\n        2 5\r\n        ```\r\n    \r\n    ???+ success \"Output\"\r\n        ```sample\r\n        4\r\n        ```","points":300.0,"partial":true,"time_limit":3.0,"memory_limit":524288,"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}}