{"code":"23olp30410a","name":"Số cách đi quân mã (Olympic 30/4 K10 - 2023)","description":"Xét một bàn cờ vua có kích thước $m \\times n$ gồm có $m$ dòng, $n$ cột. Các dòng được đánh số từ 1 đến $m$, các cột được đánh số từ 1 đến $n$. Một ô nằm trên dòng $x$, cột $y$ được kí hiệu là $(x, y)$. \r\n\r\nMột quân mã xuất phát từ một ô trên bàn cờ có thể đi đến một trong bốn ô như hình vẽ. \r\n![enter image description here][1]\r\nNgoài ra, trên bàn cờ có $k$ ô mà quân mã không được phép đi vào. Những ô này được gọi là ô bị cấm. \r\n\r\n**Yêu cầu**: Tìm số cách di chuyển của quân mã từ ô $(x, y)$ cho trước đến ô $(m, n)$. \r\n\r\n#### Input\r\n- Dòng đầu tiên ghi $4$ số nguyên $m, n, k$ và $Q\\ (1<m,n≤1000;0≤k<10; Q≤10)$; \r\n- Trên $k$ dòng tiếp theo, mỗi dòng ghi $2$ số nguyên $k_{x_i}, k_{y_i}$ cho biết ô $(k_{x_i}, k_{y_i})$ bị cấm ($1 <k_x;<m; 1 < k_y; <n$); \r\n- Trên $Q$ dòng tiếp theo, mỗi dòng ghi $2$ số nguyên $X_i, Y_i\\ (1 ≤x_i<m;1≤y_i<n)$. \r\n#### Output\r\n- Gồm $Q$ số nguyên $W_i$, mỗi số trên một dòng cho biết số cách di chuyển quân mã từ ô $(X_i, Y_i)$ cho trước đến ô $(m,n)$. Trong đó $W_i$ là phần dư của phép chia số cách quân mã di chuyển từ ô $(X_i, Y_i)$ cho trước đến ô $(m, n)$ cho $10^9$. \r\n\r\n#### Scoring\r\n - $30\\%$ test ứng với $30\\%$ số điểm của bài có $1 <m, n≤100 ; k=0; Q≤10^2$; \r\n - $20\\%$ test ứng với $20\\%$ số điểm của bài có $1 <m, n≤100;0<k≤10; Q≤10^2$;\r\n - $50\\%$ test ứng với $50\\%$ số điểm của bài có ràng buộc như đề bài.\r\n#### Example\r\n\r\n!!! question \"Test 1\"\r\n    ???+ \"Input\"\r\n        ```sample\r\n        4 5 1 3 \r\n        2 4\r\n        1 3\r\n        3 3\r\n        2 4\r\n        ```\r\n    ???+ success \"Output\"\r\n        ```sample\r\n        0\r\n        1\r\n        0\r\n        ```\r\n\r\n!!! question \"Test 2\"\r\n    ???+ \"Input\"\r\n        ```sample\r\n        4 5 0 2\r\n        1 2\r\n        3 3\r\n        ```\r\n    ???+ success \"Output\"\r\n        ```sample\r\n        2 \r\n        1\r\n        ```\r\n        \r\n  [1]: /media/pagedown-uploads/Untitled_LLjHxz4.png","points":600.0,"partial":false,"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}}