{"code":"22thtbdna4","name":"Đường đi của Robot (THTB Đà Nẵng 2022)","description":"Có một lưới ô vuông có kích thước $N × N$ được đánh chỉ số hàng từ $1$ đến $N$ (theo chiều từ trên xuống dưới) và chỉ số cột từ $1$ đến $N$ (theo chiều từ trái sang phải). Mỗi ô trong lưới được xác định vị trí bởi một cặp số $(i; j)$ trong đó $i$ là chỉ số hàng và $j$ là chỉ số cột.\r\n\r\nTại ô $(1; 1)$ người ta đặt một con robot tự hành. Mỗi lần di chuyển robot chỉ đi sang phải một ô hoặc đi xuống dưới một ô. Trong lưới ô vuông này người ta đặt một viên đá vào một số ô để làm vật cản.\r\n\r\nYêu cầu: Hãy tính xem có bao nhiêu đường đi từ ô $(1; 1)$ đến ô $(N; N)$. Biết rằng robot không thể đi vào ô có vật cản và hai đường đi được gọi là khác nhau nếu có ít nhất một ô thuộc đường đi này nhưng không thuộc đường đi kia.\r\n\r\nVD: Xét lưới ô vuông kích thước $3\\times 3$ như hình vẽ sau:\r\n![enter image description here][1]\r\n\r\nTrong lưới ô vuông $3\\times 3$ này người ta đặt viên đá vào ô $(1;3)$ và ô $(2;1)$.\r\nVới dữ kiện trên thì robot có tất cả 2 đường đi như sau:\r\n\r\n$(1;1) → (1;2) → (2;2) → (2;3) → (3;3)$\r\n\r\n$(1;1) → (1;2) → (2;2) → (3;2) → (3;3)$\r\n\r\n

Input

\r\n\r\nĐọc từ file văn bản ROBOT.INP có cấu trúc như sau:\r\n- Dòng đầu tiên chứa 2 số nguyên dương $N$ và $M$ (mỗi số cách nhau 1 dấu cách; $M < N$).\r\n- $M$ dòng tiếp theo, mỗi dòng ghi 2 số nguyên dương $i$ và $j$ (mỗi số cách nhau một dấu cách) là chỉ số hàng và chỉ số cột của ô được đặt vào đó một viên đá là vật cản.\r\n\r\n

Output

\r\n\r\n- Ghi ra file văn bản ROBOT.OUT một số $k$ là số đường đi của robot từ ô $(1; 1)$ đến ô $(N; N)$.\r\n\r\n

Scoring

\r\n\r\n - Subtask $1$ ($30\\%$ số điểm): $N \\le 10$.\r\n - Subtask $2$ ($40\\%$ số điểm): $10 < N \\le 30$.\r\n - Subtask $3$ ($30\\%$ số điểm): $30 < N \\le 100$.\r\n\r\n

Example

\r\n\r\n!!! question \"Test 1\"\r\n\r\n ???+ \"Input\"\r\n ```sample\r\n 3 2\r\n 1 3\r\n 2 1\r\n ```\r\n \r\n ???+ success \"Output\"\r\n ```sample\r\n 2\r\n ```\r\n\r\n\r\n [1]: /media/pagedown-uploads/Untitled_2BjkKBS.png","points":300.0,"partial":false,"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}}