Trên bảng h×w (h,w≤105), một quân tốt đi từ (1,1) đến (h,w), mỗi bước chỉ xuống một ô hoặc sang phải một ô. Có n≤2000 ô đen phân biệt, không gồm hai đầu mút; quân không được đi qua ô đen.
Đếm số đường đi hợp lệ modulo 1000000007.
Input
Dòng đầu chứa hwn.
Mỗi trong n dòng tiếp theo chứa tọa độ một ô cấm.
Output
In kết quả theo yêu cầu, lấy modulo như đã nêu trong phần mô tả.
Constraints
1≤h,w≤105; 1≤n≤2000; các ô cấm phân biệt và không phải hai đầu mút.
Scoring
Subtask 1 (50% số điểm): các test nhỏ trong 10 test đầu của bộ dữ liệu.
Subtask 2 (50% số điểm): không có giới hạn bổ sung.
Example
Test 1
Input
2 2 1
1 2
Output
1
Giải thích: Ô (1,2) bị cấm, nên đường đi duy nhất là xuống (2,1) rồi sang phải tới (2,2).
Lời giải tóm tắt
Phân tích: Số đường từ (r_1,c_1) đến (r_2,c_2) với tọa độ không giảm là
Phân tích:paths = C((r_2-r_1)+(c_2-c_1), r_2-r_1).
Phân tích: Thêm đích vào danh sách điểm đặc biệt và sort theo (row,column). Đặt dp[i] là số đường từ đầu đến điểm i không đi qua ô đen nào đứng trước.
Phân tích: Khởi đầu dp[i]=paths(start,p_i). Với mọi j<i có thể đi tới i, trừ
Phân tích:dp[j]·paths(p_j,p_i).
Phân tích: Vì dp[j] đã tránh mọi chướng ngại trước j, tích trên đếm chính xác các đường mà ô cấm đầu tiên trong thứ tự là j, rồi tiếp tục tùy ý tới i. Khi i là đích, dp[i] là đáp án.
Thuật toán: Cài đặt trực tiếp công thức hoặc quy hoạch nêu trên, tiền xử lý các đại lượng tổ hợp cần thiết và chuẩn hóa mọi phép toán theo modulo của đề. Các trường hợp không khả thi được loại trước khi thực hiện phép chia modulo.
Chứng minh: Mỗi đường xấu tới p_i có một ô đen đầu tiên mà nó đi qua. Sau khi sort, ô đó là một p_j trước i. Phần trước ô đó được đếm đúng bởi dp[j], phần sau độc lập và được đếm bởi paths. Các lớp theo ô đầu tiên rời nhau, nên trừ hết một lần và chỉ còn đường hợp lệ.
Độ phức tạp: Thời gian O(n²+h+w), bộ nhớ O(n+h+w).