{"code":"routes","name":"Số đường đi","description":"Cho lưới ô vuông kích thước $n× m$, ô ($1, 1$) ở góc dưới trái, ô ($n,m$) – trên phải. Có $k$\r\nô chứa chướng ngại vật, ô thứ $i$ ở tọa độ ($x_i, y_i$), $1 ≤ x_i ≤ n, 1 ≤ y_i ≤ m, i = 1 ÷ k$,\r\nKhông có chướng ngại vật ở ô ($1, 1$) và ($n, m$).\r\n\r\nRô bốt xuất phát từ ô ($1, 1$), ở mỗi bước được chuyển sang ô kề cạnh bên phải hoặc\r\nbên trên nếu ô tới không chứa chướng ngại vật.\r\n\r\nHãy xác định số lượng đường rô bốt có thể đi từ ô ($1, 1$) đến ô ($n, m$) và đưa ra số\r\nlượng theo mô đun $p$, trong đó $p$ – số nguyên tố.\r\n\r\n#### Input\r\n\r\n- Dòng đầu tiên chứa 4 số nguyên $n, m, k, p$ ($1 ≤ n, m ≤ 10^5, 0 ≤ k ≤ 100,2 \\times max{m,n} < p < 2 × 10^9$),\r\n- Nếu $k > 0$, dòng thứ $i$ trong $k$ dòng tiếp theo chứa 2 số nguyên $x_i, y_i$ ($1 ≤ x_i ≤ n, 1 ≤ y_i ≤ m$).\r\n#### Output\r\n- Đưa ra một số nguyên không âm – số lượng\r\nđường tìm được theo mô đun $p$.\r\n#### Example\r\n\r\n!!! question \"Test 1\"\r\n    ???+ \"Input\"\r\n        ```sample\r\n        5 6 3 101\r\n        2 2\r\n        3 5\r\n        4 2 \r\n        ```\r\n    ???+ success \"Output\"\r\n        ```sample\r\n        25\r\n        ```","points":1900.0,"partial":true,"time_limit":1.0,"memory_limit":262144,"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}}